点分树

树高logn

任意两点在原树上的路径一定经过他们在点分树上的LCA

维护一颗动态树,支持加入一个点,查询到某一个点的距离最小值

建立点分树,加入一个点对应在点分树上修改,每个点维护一个set,表示分治重心内所有子节点到其距离最小值,然后不难发现我们可以每次更新某个点到祖先的所有点,当一颗树失衡的时候就暴力重构他即可

查询等于跳所有父亲节点,然后对应容斥即可(我怀疑他写假了)

例题1

给出两棵大小为$n$的树, 带边权, 节点标号为1 \~ n. 对于每一个节点$i$, 找到一个节点$j$, 使得在两棵树中, $i$到$j$的距离和最小. 求$j$.

一棵树我们只需要考虑再LCA处合并即可

两棵树,对于第二个建立点分树,对于一个分治重心,两个点在第二棵树上的贡献就是一个$dep_u+dep_v-2dep_{LCA}$,另一个的贡献就是考虑建立虚树,然后再上面dfs,相当于一个带权的距离最小值,可以再点分治一波,复杂度还是$O(nlog^2n)$

std:

其实是我的另一种好写1w倍的实现方式

建立两颗点分树,假设第一个点分树LCA为a,第二棵树上的LCA为b

那么两个点x,y他们的距离就是$dist1(a,x)+dist1(a,y)+dist2(b,x)+dist2(b,y)$

$(x,a,b,dist1(a,x),dist2(b,x))$

你会发现这个四元组只会有$O(nlog^2n)$对

然后我们把x和所有a,b的都对应拿出他的最小值和次小值求和去查询即可

怎么优化?

向枚举一个a,然后考虑计算所有a子树的贡献,这样就只有b一个元素了

枚举一个点x,然后贡献$log$个祖先,再去维护最小值和次小值,查询即可

边分治

三度化

每次找到最能均分子树的那条边,然后分开

好处是每次只有两个分治结构,是一个二叉树

然后就是$dis(x,a)+(a,b)+dis(b,y)$

P4565 [CTSC2018]暴力写挂

点分治,然后考虑把儿子都染成不同的颜色,我们只算不同的颜色合并带来的贡献

于是我们考虑建立虚树,然后虚树上dp,(其实就是枚举LCA.....),因为求的最大值,所以我们只需要设$f_{u,0/1}$表示以u为根的子树中,最大的/次大的w(x),钦定两个颜色不同,以及对应的颜色即可

然后合并子树等价于4个pair合并不同颜色计算答案,也很简单qwq

但是常数不够优秀,告诉我们要边分治

将树三度化,然后考虑还是染色,现在我们的距离变成$dis+dis+(a,b)$所以第一个$dis$就是点权,然后考虑还是上述过程,记录子树中最大的黑和最大的白,在合并的时候计算贡献即可

时间复杂度还是$O(nlog^2n)$,但是想想就很阳间不需要很麻烦的转移,所以快的一比

老师告诉我们边分树合并

枚举第二棵树上的LCA为u,然后考虑计算所有以u为LCA的答案

式子变为$\frac{dep_x+dep_y+dis_{x,y}}{2}-dep'_{u}$

前面的式子最大值,这个可以边分治完成

然后我们就发现我们只计算不同子树的贡献,而他们的边分树都是二叉树

因此可以边分树合并

P4220 [WC2018]通道

一句话题意,求$max(dis1(a,b)+dis2(a,b)+dis3(a,b))$

第一棵树要边分治吧,然后深度搞成点权,建立第二棵树的虚树,再考虑怎么在上面统计答案

坏了,我们看看式子

此时点权是$dist1(x,a)+dep_2(y)+dep_3(x)$

第二棵树上就要实现$Ans=max{W(x)+W(y)-2dep_{LCA}-2dep3_{LCA}}$

哇!你发现他不是人做的!

但是但是!!你再仔细思考为什么能做三颗树啊

W(x)一定大于0,因此直径信息可以合并

于是发现这个东西满足直径的性质.......无论带不带权都是直径啊

所以我们就可以维护黑点或者白点的直径啊,复杂度在合并,我们可以$O(1)LCA$来快速合并子树直径就能快很多

这里好像只能边分治....因为点分治像上个题一样维护两个不同颜色的最大的/次大的直径,每次交错合并的时候更新答案...好像你无法去更新新直径的大小,就是某种颜色合并后新直径大小无法计算,所以自闭了

区间取模,模数固定,区间加区间和

分块

对于一个大块维护$(x+a)\%m+b$的tag

问题在于怎么全局加再全局取模

考虑维护所有数在$\%m$后的值排序

然后序列加再取模就相当于<m-x的数回加上x,>=m-x的数会减去$(m-x)$

然后你思考一下我们怎么合并tag

$((x+a)\%m+b)\%m+d=(x+(a+b)\%m)\%m+d$

然后tag的修改方式知道了我们就好知道怎么查询一个块内的答案了

二分那个m-x的分界点即可

复杂度$O(n\sqrt n logn)$,我们重构使用归并排序就能$O(n\sqrt{nlogn})$

$(qBlogB+q\frac{N}{B}*log(B))$

或者$O(qB+q\frac{N}{B}log(B))$,B取$O(\sqrt {nlogn})$

远古集训队互测题

区间子区间平均值最大值

二分答案,然后就变成区间减,区间子串和最大值了吧,然后就直接线段树实现带修区间最大值即$O(nlog^2n)$??

看错了是子区间和/长度-1最大值

自闭了

$(i,pre_i)$

$(i,pre_{i-1})$

两类点,相当于一个A类和一个B类的斜率最大值

那么就是前缀A类下凸壳然后后缀B类上凸壳的两个

预处理块内的答案

对于每个询问答案只可能有几种情况,1. 同一块内

2. 单独左右
3. 一个在左一个在右

第一类解决了

这2类都可以单独拿出来按顺序加点,不断维护A,B点的上凸壳,然后每个点都二分一下即可,很好实现

复杂度就是$O(\sqrt n\log n)$

第三类就更简单,单独建立凸壳然后二分即可

然后就是整散之间

我们考虑离线所有,然后处理块$[a,b]$对于每一右端点的答案$q_R$

即块[a,b]对于$[b+1,r]$的答案,这个只需要记录一个下凸壳即可

然后同样处理[a,b]对于所有左端点的答案,$p_L$

如果要强制在线要用$O(n\sqrt n)$保存下来,否则我们只需要直接离线统计每一块的贡献,就是$max p_L,q_R$

区间众数,强制在线

考虑算块$[l,r]$的答案那么就可以直接加入零散块回答询问了

怎么预处理啊暴力扫吧

然后考虑现在有零散块,如果众数不出现在两端就是$f_{bl,br}$

否则就是只有两端共$O(\sqrt n)$种,我们可以暴力二分每个位置计算出现次数即可

我们这样有log,考虑干掉log

预处理$posx$表示x这个数第i次出现在哪个位置

先拿到整块的答案$x$,出现mx次

然后我们考虑当前位置快速定位到posx数组,如果这个位置+mx+1还是$\leq r$,就mx++并更新最大数继续询问即可

mx最多只会更新$O(\sqrt n)$次

因为如果多余这个次数整块就不做人了...

然后徐强强告诉我们可以处理一个$O(n\sqrt n)$代表次数的前缀和数组,查询就变成了$O(n\sqrt n)$了,因为我们可以直接枚举

三四元环计数

有向图是度数大优先编号大优先

三元环计数可以像有向图连好,然后一个点在无向图上向枚举的点直接打标记,再从那个点枚举有向图把经过打标记的点加上答案

这样每个点都只会被在最大编号的统计一次

四元环计数就是边定向,然后向枚举u相邻的v是原图中的边,然后v再去枚举原图的边打标记,然后再去枚举定向边统计答案

还有$O(\frac{n^2}{32})$

就是每个点的邻接矩阵搞出来,bitset,然后两两枚举and起来,对于任意的交集大小g,会产生$g*(g-1)/2$,然后考虑这样会把一个算重,除2即可

五六圆环计数是$O(m^2\sqrt m)$,依次类推..

上午

最近点对问题

对于一个点p,假设两边的最小距离为d,那么我们只需要考虑沿着分界线左右各分一个大小为d的矩形,只有这个矩形内的点可能满足条件

那么可以证明这样的点相当少,不能放很多进去

所以所有点按照y值排序,然后你会发现x坐标同样不能超过d,

右边按照双指针扫一下即可,每次$O(n)$更新,这个n大小不会超过7

排序不同$O(nlogn)$或者$O(nlog^2n)$

还有随机算法

先$randomshuffle$

假设前i个点答案为r

我们可以把整个面分块,每2r分一块,然后每个点插入的时候就只需要查询所在块内的所以点的答案了(这个分块好像不太懂)

那么对于第i+1个点,如果能够更新答案就整个重构,这个期望重构次数为$(\frac{1}{i})$

复杂度就是$O(nlogn)$

BZOJ3636

每个区间选取若干个长度为L的不交区间和最大

线段树

考虑分治计算跨过分治中点的答案

假设当前分治区间为$[l,r]$,同时中点为$mid$

dp可以求出,考虑了前i个数,当前已经选了j个数,然后转移考虑选不选下一个数

然后处理询问的时候合并一下即可,枚举左边选了多少数x,然后右边选了$L-x$个数,拼起来即可

这一个询问只会被一个端点劈开,然后劈开的那个区间我们对应回答这个询问即可,总之用$dp_{i,j}$表示从i开始到mid最后一段区间选了j个的最大值总可以合并的

你会发现合并区间复杂度为$O(L)$,故为$O(nlognL+qL)$

这个就是猫树的一个例题

CF1100F Ivan and Burgers

扫描线,从左向右扫

每个线性基记录两个信息,这个数是什么,这个数是第几次出现的

然后每次加入一个点,更新线性基,最高位的一定可以更新,然后和最高位交换,异或,再用那个和剩下位比较,越靠后的保留

这样做一遍复杂度就是$O(nlogV)$

然后回答询问考虑只使用大于等于L的能凑出的最大数是什么即可

复杂度$O((n+q)logV)$

两个log的做法,分治

先预处理$l->mid$的线性基信息$O(nlognlogV)$

然后考虑处理所有跨过分治中心的询问,可以直接线性基合并,$O(log^2V)$

就有$O(nlognlogV+qlog^2V)$

但是也是离线的被爆锤

[模板]三维偏序

对于第一维排序

第二维考虑分治,cdq一下,只要钦定左边的第一维一定小于右边的第一维,第二维就能排序了

第三维可以树状数组,就是我们双指针尺取归并的时候,把第三维插入树状数组中,然后直接查询b,c两维都偏序的即可

两次归并的做法我们第二层要保证哪些是要对哪些产生贡献的,然后递归第三层去吧第三维排序

排列有一个互不相同的优势,我们考虑每两维做一个二维偏序,然后考虑贡献,三维都偏序被计算了3遍,剩下正好二维偏序的都计算了一遍

而一维偏序不存在,因此是$\frac{ans-\binom{n}{2}}{2}$

ans是三遍的总和

加强版

代价和改为$(x+1)^2$

计算方法就是考虑dp,然后分治消除掉单调不降那一维的限制

$dp_i=max_{v_j\leq v_i}(dp_j-(i-j+1)^2)$

按照最小值分治,每次新加入决策点,那么我们就是不对的

考虑分治,其实这个限制就是一个平凡的二维偏序

然后左边右边都按照v排序,然后左边加入的时候相当于加入新决策点,但是你会发现此时横坐标不单调

所以我们按照$v_i$排序,然后按照i去归并,这样一定能保证横坐标单调,也就直接建立凸包更新决策就显然了

整体二分

$solve(l,r,ql,qr)$

考虑mid对于那些合法,分到左边和右边即可

AT1998 [AGC002D] Stamp Rally

二分答案

然后考虑把这些边加入,存不存在一条从x到y的长度为$z-1$的路径...

如果x,y所在连通分量点数大于等于z就合法/ll

如何证明啊?

因为不是简单路径同时是不计重复的点吧

所以直接并查集即可...

P3332 [ZJOI2013]K大数查询

可重集啊没意思了

直接整体二分,修改和查询保持相对顺序的情况下可以同步二分递归

假设答案为x,修改就等于单调加1,询问就是区间求和,那么如果答案偏大(大于k,就说明现在区间内小于等于x的太多了,询问就向右边放,否则就向左边放

然后每个修改和询问的一层都可以用树状数组维护

不可重集能树套树的说

最值分治

每次处理所有跨过最大/小值的询问说不定就能消掉一个限制~

然后我们如果能用$min(r-x,x-l)$的复杂度解决就$O(nlogn)$了,复杂度分析和启发式分裂一样!

#loj6198. 谢特

两两后缀贡献最大值,贡献定义为最长公共前缀+$(w_ixorw_j)$

SAM!

都插入后缀,然后LCP就是后缀树上的两个点的LCA

然后相当于统计不同子树异或最大值,这个可以每次插入一个tire启发式来合并查询

后缀数组!

对于一个后缀数组h最小值,我们对于跨过他的LCP处理,那么就是预处理一个区间trie,然后拿短的一边向长的一边查询即可

可持久化trie是区间trie的一种实现方法,很ez

甚至有老哥告诉我们再笛卡尔树上启发式合并....你有点可怕

$O(npolylog)$

NWERC-2017 Factor-Free Tree

就是给出点权的中序遍历,然后询问能不能建一棵带权树满足每个节点的子孙节点都和该节点权值互质

首先预处理某个节点能互质的最大区间,那么可以认为这个数就是这个区间的最大值,然后找到完全包含某个区间的数做根就好了,每次建树相当于二维数点就T到天上QAQ

这个预处理方法可以考虑每一个质因子的前驱是什么

于是我们有一个神仙启发式分裂!!我们每次从两端向中间搜索,那么找到第一个合法的位置会快很多,实际上最坏才有$O(nlogn)$qwq

证明就是如果我们都能够卡满区间的分裂那么我们就是完整的分治$O(nlogn)$结构

否则就是$O(min(mid-l,r-mid))$,启发式合并复杂度qwq

重心

就是最大子树最小的点

相对于整个子树做一遍,然后点分治

Tree

树上距离小于等于k的点对数

点分治,统计到分治中心的所有路径

然后这些可以直接把前$i$棵子树放进map里面,然后对于第$i$棵查询一下一个前缀最小值,这个可以排序twopointers,都不需要值域

P4292 [WC2010]重建计划

二分答案

然后点分治,查询边数$[l,r]$的一个最大权路径

单调队列

考虑分治中心所有子树按照深度排序从小到大处理,然后此时我们会发现复杂度就是对的了,每次可以重构整个单调队列!

树的难题那道题也是可以的....因为我们可以把一些相同颜色的树压成一个序列

#3225. 「PA 2019」Podatki drogowe

权值定义为$n^{p_i}$

然后询问路径权值第k大

如果权值没有这样定义,我们直接二分答案,然后点分治,然后统计出所有路径权值中小于他的就好了

std

注意到不会进位

比较两个路径大小只需要从高到低比较即可,线段树维护一下哈希值就能路径比较变为$O(logn)$?

然后二分答案不行,我们可以二分路径!

就是随机一个路径,他的权值在$[l,r]$之间,然后用这个作为mid即可

注意如果$[l,r]$没有多少路径就要都拿出来排序了....

哈希比较方法是这样的:对于一个数,所有二进制位建立线段树,然后如果左子树哈希值相同向右递归,否则向左递归,最后我们比到底层看那个位置谁的1多即可

然后点分治采用总的任意的减去单独在每个子树内部的,就是加权,任意两个拼就是-1的系数,否则就是1的系数,点分容斥

然后求小于等于x的贡献直接twopointer即可,虽然我们数大小很抽象,但是单调性还是有的

复杂度高达三个$log$ qwq

经典问题：区间凸包

给出一个平面上的点的序列，每次询问一个区间的凸包的面积，保证横坐标单调递增，强制在线。

妙 啊 !

这个问题可以猫树!

我们建立prel的凸包,sufl的凸包,然后直接用一条公切线就能合并凸包!

这里凸包只有x单调插入,因此简单的可持久化数组即可