1、专题讨论：分治方法专题讨论：分治方法AC_AerolightAC_Aerolight2013.4.282013.4.29 Fuzhou2013.4.282013.4.29 Fuzhou2022-5-211 1PREFACE今天首先讨论的是一种特殊的分治方法，在OI界初见于陈丹琦2008年的集训队作业中，因此也被称为CDQ分治。随后将讨论一些利用了分治思想的其他算法。这节课的目的是科普，因此题目会较简单，讲解也会比较详细。如果对该算法或对特定问题已有深入了解可以跳过不听，但不要打扰其他同学。Lets begin.2022-5-212 2PREFACE先看几个常见的递归复杂度分析。T(n)=2T(
2、n/2)+O(kn)的解是T(n)=O(kn log n)Master TheoremT(n)=2T(n/2)+O(kn log n)的解是T(n)=O(kn log2 n)T(n)=2T(n/2)+O(k)的解是T(n)=O(kn)一棵N个节点的线段树上有几个节点？K是一个和N无关的多项式2022-5-213 3INTRO：归并排序给定排列P，求排列的逆序对数量。P的长度=100000。要求O(nlogn)定义归并排序过程Merge(l,r)Merge(l,r)Merge(l,mid)Merge(mid+1,r)Count(l,mid,mid+1,r)只需要考虑左右两段之间造成的逆序对，段内
3、的逆序对由递归解决2022-5-214 4NOI2007 CASH有两种金券，金券按比例交易：买入时，将投入的资金，购买比例为Ratei的两种金券；卖出时，卖出持有的一定比例的金券。已知未来n天两种的金券价格Ai、Bi，初始资金为s，求最大获利。为使获利最大，交易时显然应该全部买进或卖出。1=n-bi/ai上面这个式子的左边，一般记成slope(j,k)2022-5-216 6NOI2007 CASHSlope(j,k) -bi/ai令Gi = ratei*fi，在二维平面上定义点Xi=(Fi,Gi)Slope(j,k)就是通过Xj和Xk的斜率维护一个点集X，支持以下两个操作：1)在第一象限的
4、任意位置插入一个点2)给定负数斜率K，求所有斜率为K且过点集中任意点的直线在Y轴上的最大截距操作2最终用到的点都会在点集的上凸壳上维护点集X的凸包，支持动态插入和斜率查询平衡树结构 O(nlogn)2022-5-217 7NOI2007 CASH算法存在的问题边界情况众多难写难调观察操作2中，提供的斜率值是-bi/ai，可以预处理得到而和F的取值无关这意味着在插入节点Xi时，已经可以确认它对询问j(ji)带来的影响引入分治思想2022-5-218 8NOI2007 CASH定义过程Solve(L,R)假设运行Solve(l,r)可以得到Fl到Fr的值。L,mid区间里的询问，可以直接递归Sol
5、ve(l,mid)解决。mid+1,r区间里的询问K，会受到mid+1,k这些点的影响，以及l,mid的影响。前半部分可以递归解决。Solve(l,r)递归调用Solve(l,mid)整体考虑l,mid间的点对mid+1,r间询问的影响。递归调用Solve(mid+1,r)2022-5-219 9NOI2007 CASH整体考虑l,mid对mid+1,r的影响给定点集X和一系列询问每个询问是一个负数斜率回答所有斜率符合且通过点集X中任意点的直线中，Y轴的最大截距是多少只要考虑点集X的上凸包。对于每个询问，在凸包上二分即可。这一步的复杂度是O(nlogn)，这里n=r-l。2022-5-2110
6、10NOI2007 CASH时间复杂度？Solve(l,r)的复杂度是O(nlogn)T(n)=2T(n/2)+O(nlogn)T(n)=O(nlog2n)离最优化还有距离。需要log n的地方1) 求点集凸包2) 二分答案2022-5-211111NOI2007 CASH1) 点集凸壳合并两个凸壳的时间复杂度是O(n+m)Solve(l,r)结束后返回Xl.Xr的凸壳单步O(n)，总体O(n log n)2) 二分答案放弃二分，离线处理把点集凸壳和所有询问排序，用两个指针扫描2) 对询问排序提前对询问进行一次归并排序，存储所有中间结果为什么不能在Solve()时进行归并？预处理复杂度O(nl
7、ogn),主递归中单步O(n)T(n)=2T(n/2)+O(n),T(n)=O(nlogn)2022-5-211212NOI2007 CASHSolve(l,r)是递归函数如何消除递归？手工栈模拟递归存储中间过程？T(n)的解不变，但常数减小。总结1) 分治思想-只考虑跨立作用2) 段内影响忽略不计-问题离线化2022-5-211313WF2011 MACHINE WORKS你的公司获得了一个厂房N天的使用权和一笔启动资金，你打算在这N天里租借机器进行生产来获得收益。可以租借的机器有M台。每台机器有四个参数D,P,R,G。你可以在第D天花费P的费用（当然，前提是你有至少P元）租借这台机器，从第
8、D+1天起，操作机器将为你产生每天G的收益。在你不再需要机器时，可以将机器卖掉，一次性获得R的收益。厂房里只能停留一台机器。厂房里只能停留一台机器。不能在购买和卖出机器的那天操作机器，但是可以在同一天卖掉一台机器再买入一台。在第N+1天，你必须卖掉手上的机器。求第N+1天后能获得的最大资金。2022-5-211414WF2011 MACHINE WORKS数据范围租借天数D=109初始资金C=109机器数N=105对于每个机器：租借日Di=D买入价Pi和卖出价Ri满足1=RiPi=109每日收益Gi满足1=GiPj。O(n2)2022-5-211616WF2011 MACHINE WORKSF
9、i = Max (Fi-1, Fj-Pj+Rj+Gj*(Di-Dj-1)FjPj令Aj=Fj-Pj+Rj-Gj*Dj-Gj那么Fi = Max(Fi-1,Aj+Gj*Di)和上一题一样了。注意到斜率Di是不变的，因此可以对整个F1,Fn进行分治。复杂度O(nlogn)，和平衡树维护凸壳同阶2022-5-211717WF2011 MACHINE WORKSFi = Max(Fi-1,Aj+Gj*Di)在平面上有若干直线y=Gj*x+Aj维护一个直线集，支持以下两类操作插入一次函数y=kx+b给定询问D，求所有函数在x=d上的最大值维护一系列半平面交对偶问题？2022-5-211818BOI200
10、7 MOKIA有一个2000000*2000000的棋盘，每个格子上有一个数字Ax,y，现在要执行两类操作：Add x y a：Ax,y += aQuery x0 y0 x1 y1：询问矩阵(x0,y0)-(x1,y1)内所有格子的数字和。Add操作数=160000 Query操作数=100002022-5-211919BOI2007 MOKIA棋盘大小和询问数相差巨大，所以肯定要离散化。二维线段树维护？MLE+TLE二维树状数组+Hash？Hash常数过大空间怎么开？2022-5-212020BOI2007 MOKIA和之前的想法类似，定义操作Solve(L,R)Solve(L,R)应当能够
11、处理L,R之间的所有操作Solve(L,R)Solve(l,mid)处理l,mid中操作对mid+1,r中操作的影响Solve(mid+1,r)如何处理？2022-5-212121BOI2007 MOKIA前半部分的Add对后半部分的Query造成的影响给定带权点集P=(Xi,Yi)，Q个询问(x0,y0,x1,y1)，对于每个询问，输出在对应矩形内的点权之和。在列上对询问进行差分，将一个询问拆成2个所有点和询问按Y排序，线段树维护在两维上对询问进行差分，将一个询问拆成4个所有点和询问按Y排序，树状数组维护T(n)=2T(n/2)+O(nlogn)T(n)=O(nlog2n)2022-5-21
12、2222VIOLET 3天使玩偶维护二维点集P，支持以下两个操作(1)插入点(x,y)(2)给定询问(x,y)，求点集中离询问点最近的点距离定义为曼哈顿距离Dis(P1,P2)=|x1-x2|+|y1-y2|N,m=300000X,y=1000000k-d树能不能做2022-5-212323VIOLET 3天使玩偶去除Dis(P1,P2)的绝对值符号分4种情况讨论：左上，左下，右上，右下只需要考虑一种情况（答案在询问的左下）维护点集P，支持以下操作(1)将(x,y)插入点集(2)给定询问(x,y)，求满足dis(p1,p2)=(x-x)+(y-y)=x+y-(x+y)最小的点问题转为求x+y最
13、大的点没有操作1的情况对x排序，对y维护树状数组2022-5-212424VIOLET 3天使玩偶定义操作Solve(l,r)，处理l,r之间的询问Solve(l,r)Solve(l,mid)考虑l,mid中的点对mid+1,r中询问的影响Solve(mid+1,r)给定带权点集P(x,y)，权值为x+y，给出Q个询问(x,y)，查找x=x,yPj & QiQj，称I比J有能力现在要求出最长的一个序列A=(A1,A2,At)，满足Ai比Ai+1有能力N=100000。为了简单起见，P和Q都是1到N的排列。把人按照Pi排序，问题变为求序列Qi的LISFi = Max(Fj | ji & QjPj
14、 & QiQj & RiRj，称I比J有能力现在要求出最长的一个序列A=(A1,A2,At)，满足Ai比Ai+1有能力N=40000。为了简单起见，P,Q,R都是1到n的排列2022-5-2127273D PARTIAL ORDER首先可以按照Pi把人排个序。现在要求的是满足ij,QiQj,RiRj的最长序列。用Fi表示以第i个人结尾的最长序列Fi = MaxFj | ji,QjQi,RjRi +1怎么搞？线段树套平衡树/可持久化线段树O(nlog2n)2022-5-2128283D PARTIAL ORDER尝试在这个问题上进行分治。定义过程Solve(l,r)，能够得到Fl.Fr的值Sol
15、ve(l,r)Solve(l,mid)处理l,mid中元素对mid+1,r中Fx取值的影响Solve(mid+1,r)Fx = MaxFj | jx,QjQx,RjRx +11) x在l,mid中：集体处理2) x在mid+1,r中：由递归解决 2022-5-2129293D PARTIAL ORDER处理l,mid中元素对mid+1,r中Fx取值的影响维护带权点集X=(Qi,Ri) (l=i=mid)，权值Fi支持询问：给定点(Qj,Rj) (mid+1=j=r)在点集X中寻找一个点(Qi,Ri)使得QiQj且RiPj & QiQj & RiRj & SiSj，称I比J有能力对每一个人，输出
16、任意一个比他有能力的人编号，或声明没有人比他有能力。N=40000简单起见，P,Q,R,S都是1-n的排列。树套树套树？怎么写树套树？2022-5-213232SIMPLIFIED 4D PARTIAL ORDER首先把元素按Pi排序。对每个i，要判断是否有一个j满足ji,QjQi,RjRi,SjSi.条件太多了，不好做。问题等价于Min(Sj|ji,QjQi,RjRi) Si求Min(Sj | ji,QjQi,RjRi)回忆上一题Fi = MaxFj | ji,QjQi,RjPj & QiQj & RiRj & SiSj，称I比J有能力现在要求出最长的一个序列A=(A1,A2,At)，满足A
17、i比Ai+1有能力N=20000树套树套树？树套树？2022-5-2134344D PARTIAL ORDER将元素按照Pi排序。用Fi表示以第i个人结尾的最长序列Fi = MaxFj | ji,QjQi,RjRi,SjTLE+MLEHash动态节点，三维树状数组-？我们尝试一下分治。2022-5-2135354D PARTIAL ORDER定义Solve(l,r)，解决Fl到Fr的问题。Solve(l,mid)考虑l,mid中的点对mid+1,r中F取值的影响Solve(mid+1,r)整体考虑给定带权点集X=(Qi,Ri,Si) l=i=mid，权值Fi给定(r-mid)个询问(Qj,Rj
18、,Sj) mid+1=j=r对于每个询问，回答点集中满足QiQj,RiRj,SiSj的最大权值。离线操作按Qi排序。询问满足RiRj,SiSj的点的最大权值2022-5-2136364D PARTIAL ORDER询问满足RiRj,SiSj的最大权值线段树套平衡树？树状数组套平衡树？再分治一次定义分治过程Solve2(l,r),用于处理Solve(l,r)中l,mid中的点对mid+1,r中F值的影响。Solve2(l,r)Solve2(l,mid)处理(l,mid)中点对(mid+1,r)中询问的影响Solve2(mid+1,r)和Solve(l,r)有什么区别？2022-5-2137374
19、D PARTIAL ORDERSolve(l,r)Solve(l,mid)创建一个创建一个 l,rl,r 的副本并按照的副本并按照QQi i 排序排序Solve2(l,r)Solve(mid+1,r)Solve2()的工作维护带权点集X=(Ri,Si)，支持两个操作1) 将一个点(Ri,Si)插入X，权值Fi (l=i=mid)2) 给出询问(Rj,Sj)，求一个权值最大且满足RiRj,SiSj的点在Solve2()上定义分治过程。2022-5-2139394D PARTIAL ORDERSolve2(l,r)Solve2(l,mid)处理l,mid的点对mid+1,r的询问的影响Solve2
20、(mid+1,r)维护带权点集X=(Ri,Si) (l=i=mid)，权值Fi支持询问：给定点(Rj,Sj) (mid+1=j=r)在点集X中寻找一个点(Ri,Si)使得RiRj且SiSj，满足以上条件的点中取权值最大的。很眼熟？离线处理。同三维情况，排序后树状数组或线段树维护。2022-5-2140404D PARTIAL ORDER时间复杂度分析定义T2(n)为Solve2(l,r)的时间复杂度。T2(n)=2T2(n/2)+O(nlogn)T2(n)=O(nlog2n)定义T(n)为Solve(l,r)的时间复杂度。T(n)=2T(n/2)+T2(n)=2T(n/2)+O(nlog2n)
21、T(n)=O(nlog3n)2022-5-214141100D PARTIAL ORDER有N个人，每个人有100种能力值Pi1,Pi2,.,Pi100。如果对于1=kPjk，称I比J有能力现在要求出最长的一个序列A=(A1,A2,At)，满足Ai比Ai+1有能力NRi，指的是Li,Li+1,m,1,2,Ri-1,Ri。每场流星雨有一个数量Ai，表示这场流星雨将会为波及的每个观察站提供Ai单位的陨石。每个国家都拥有陨石收集数的目标Wi。对于每个国家，输出它在第几场流星雨后可以达到目标。N,M,K=3*105,Ai,Wi AC?T(x)=O(xT(x)=O(x* *klogmklogm) )！2
22、022-5-214848POI2011 METEORTLE的原因在于(1)的单步复杂度和递归长度x无关。维护全局线段树O(logm)模拟和撤销撤销一次流星雨在运行Solve(l,r)之前，线段树存储了第1次到第l-1次流星雨的情况在运行Solve(l,r)之后，线段树存储了第1次到第r次流星雨的情况用+l,r表示模拟l,r这段流星雨，-l,r表示撤销如何写Solve(l,r,S)?2022-5-214949POI2011 METEORSolve(l,r,S)+ l,mid分割点集S- l,midSolve(l,mid,S1)Solve(mid+1,r,S2)模拟流星雨的时间复杂度T(x)=2T
23、(x/2)+O(O(xlogmxlogm) )T(x)=O(T(x)=O(xlogxlogmxlogxlogm) )整个算法的复杂度是O(klogklogm+nlogklogm)。AC。2022-5-215050POI2011 METEOR并行分治对于每个国家的询问，一开始的答案区间都是1,n。同时对所有国家进行二分查询主算法Solve执行一次整体二分，调用logk次每个国家答案区间的中点是midX询问第X个国家在midX时是否收集到Wx的陨石对midX排序，离线处理顺序模拟所有流星雨，到第midX个时统计答案如果答案Wx那么区间变成mid+1,r否则l,midLogk次算法后，每个答案区间长
24、度为1，直接输出T(n)=logk*(k*logm+n*logn)2022-5-215151矩阵乘法（梁盾）给定n*n的矩阵A给定Q个询问(x1,y1,x2,y2,k)，询问子矩形x1,y1x2,y2中的K小数。N=500Q=mid)，判定矩形内权值是否k准备分治Solve(l,r,S)处理所有答案落在l,r之间的询问分割S到Solve(l,mid,S1)和Solve(mid+1,r,S2)中构造Di,j(mid)维护全局二维树状数组需要加的点只有(i,j) | L=Ai,j=mid2022-5-215353矩阵乘法（梁盾）时间复杂度统计单次操作可以视为log2nF(n)=2F(n/2)+O(
25、log2n)F(n)=O(nlog3n)优化？规避二维数据结构将询问和插入点集按x进行归并排序，维护y的树状数组F(n)=2F(n/2)+O(nlogn)F(n)=O(nlog2n)2022-5-215454ZJOI2013 K大数查询有n 个位置和m 个操作。操作有两种，每次操作如果是1 a b c 的形式，表示往第a 个位置到第b 个位置每个位置加入一个数c。如果操作形如2 a b c 的形式，表示询问从第a 个位置到第b 个位置，第c 大的数是多少。n,m=50000操作1中，c=n操作2中，c=maxlongint2022-5-215555ZJOI2013 K大数查询2 51 1 2
26、11 1 2 22 1 1 22 1 1 12 1 2 3【样例输出】121第一个操作后位置1 的数只有1，位置2 的数也只有1。第二个操作后位置1的数有1、2，位置2 的数也有1、2。第三次询问位置1 到位置1 第2 大的数是1。第四次询问位置1 到位置1 第1 大的数是2。第五次询问位置1 到位置2 第3大的数是1。2022-5-215656ZJOI2013 K大数查询常规的数据结构线段树套平衡树二分答案？外层线段树表示插入的数大小，内层表示坐标动态分配单一询问的情况二分答案+维护线段树等等准备分治Solve(l,r,S)用于处理答案落在l,r之间的所有询问分割S集合2022-5-2157
27、57ZJOI2013 K大数查询分割集合已知所有询问在L处的回答，求在MID处的回答所有的操作1中，只有l=c=mid的有作用按时间排序后维护树状数组时间复杂度单步的复杂度均摊后不超过O(nlogn)级别T(n)=2T(n/2)+O(nlogn)T(n)=O(nlog2n)总结一下上面三题的共性2022-5-215858PACKAGE有N个物品，每个物品的重量是Wi,价值是Gi每个物品只能取一个给定Q个询问，每个询问由两个数(X,I)组成给定最大容量为X的背包，使用除了第i件物品以外的所有物品，能够得到的最大价值之和N=100询问中的X=10000Q=1000000怎么做？2022-5-215
28、959PACKAGE离线操作只有1个询问/所有询问的I相同的情况0/1背包O(nm)维护0/1背包O(m)将一个物品放入背包。同样，定义+l,r表示把l到r的物品放入背包+l,r的复杂度是O(nm)准备分治对重量分治对物品对物品IDID分治分治2022-5-216060PACKAGE定义Solve(l,r)，用于处理所有l=l=i i=r=r的询问定义Solve(l,r,S),用于处理所有l=i=r的询问S是一个0/1背包，放进了除了除了 l,rl,r 之外之外的其他物品Solve(L,L,S)时，回答所有I=L的询问Solve(l,r,S)Solve(l,mid,S+mid+1,r)Solv
29、e(mid+1,r,S+l,mid)时间复杂度分析T(n)=2T(n/2)+O(nm)T(n)=O(nmlogn)2022-5-216161HNOI2010 CITY有一个N个点M条边的无向图，每条边有边权Wi给定Q个操作(Ei,Zi)，表示将第Ei条边的费用改为Zi每次操作之后，输出当前无向图的最小生成树权值N=20000,M=50000,Q=50000,Wi,Zi=108NO SPOILERS PLZ.特殊情况：修改后边权不加。2022-5-216262HNOI2010 CITY修改后边权不加的情况修改(x,y)的权值时，最小生成树的边构成边构成1）不变2）(x,y)加入最小生成树，另外一
30、条边退出2)发生的条件原MST上x到y路径上的最大值大于(x,y)的权值维护MST支持加入一条边，删除一条边，查询路径最大值Link-Cut Tree维护无根树2022-5-216363HNOI2010 CITY修改后边权不减的情况？预处理之后倒着做就行了。不管怎么样，这个问题是离线的离线的2022-5-216464HNOI2010 CITY能不能对操作序列进行分治？定义Solve(l,r)，用于处理L到R的操作并得到答案Solve(l,r)Solve(l,mid)处理l,mid的加边对mid+1,r的询问的影响Solve(mid+1,r)一条边对一个询问的影响难以表示。2022-5-2165
31、65HNOI2010 CITYSolve(l,r)Prepare(l,r)Solve(l,mid)Solve(mid+1,r)对l,r分治的优势：可能改变可能改变的边权数是O(r-l)，可能远小于O(m)区间里的MST查询结果有相似性。2022-5-216666HNOI2010 CITY：STEP 1假设G是一个带权无向图的边集，S是G的一个子集。将S中边权设为+inf后，T是图G的最小生成树。也可以说T是G-S的MST定理1：不管S中的边权怎么变化，G的最小生成树T将属于属于TS。对于任意一条不属于TS的边，我们可以在T中找到链接它两端的一条路径。由于这些边取值都和S无关，无论S权值怎么更改
32、，这个环上这条边最大，不会进入MST2022-5-216767HNOI2010 CITY：STEP 1假设G是一个带权无向图的边集，S是G的一个子集。将S中边权设为+inf后，T是图G的最小生成树。也可以说T是G-S的MST定理2：在定理1的前提下，我们可以在不影响T的情况下，将G的边数边数缩减到n+|s|-1以下。直接运用定理1，G-S的最小生成树最多有N-1条边。其他的边不可能在T中，我们可以安全地删除掉。这一步被称为Reduction，效果是减少了G的边数。复杂度同MST是O(mlogm)，m=|G|。2022-5-216868HNOI2010 CITY：STEP 2假设G是一个带权无向
33、图的边集，S是G的一个子集。将S中边权设为-inf后，T是图G的最小生成树。定理3：不管S中的边权怎么变化。G的最小生成树T将包含包含T-S。考虑将S的权值一条边一条边提升的情况。每提升一条边权值，MST要么不变，要么就是S中的一条边离开，一条新边加入。无论如何，T-S这些边都不会离开MST。2022-5-216969HNOI2010 CITY：STEP 2假设G是一个带权无向图的边集，S是G的一个子集。将S中边权设为-inf后，T是图G的最小生成树。定理4：在定理3的前提下，我们可以在不影响T的情况下，将G的点数点数缩减到|s|+1以下以下。假设已经对图进行了Reduction。根据定理3，
34、由于T-S的边不离开MST，我们可以将这些边连接的点合并为联通分量，将联通分量视为节点。之后根据节点归属更新边表即可。这一步被称为Contraction，效果是减少了G的点数。复杂度同MST，O(mlogm)2022-5-217070HNOI2010 CITY根据上面的推论，我们可以得到结论：给定一个图G和操作序列S，可以在O(mlogm)时间内通过reduction-contraction将图的边数缩小到n+|s|-1，点数缩小到|s|+1而保持求解过程的正确性。定义分治过程Solve(l,r)用于解决L到R区间的问题。为了方便起见，我们将图G作为参数传递。定义分治过程Solve(l,r,G
35、)解决L到R区间的问题。2022-5-217171HNOI2010 CITYSolve(l,r,G)Reduction(G)Contraction(G)Solve(l,mid,G)Solve(mid+1,r,G)Recover(G) /用于撤销Reduction-Contraction的影响边界情况：Solve(l,l,G)2个点和1条边！直接判断即可2022-5-217272HNOI2010 CITY时间复杂度分析在执行Solve(l,r,G)时，G的点数和边数都是O(r-l)的在第一次分治之前，对原图做一次R-C分治之后由归纳假设和R-C过程易得原证明成立R-C(n)的时间复杂度是O(nl
36、ogn)Recover的复杂度不会高于R-C(n)的复杂度T(n)=2T(n/2)+O(nlogn)2022-5-217373CONCLUSION基于时间（或阶段、顺序）分治牺牲时间复杂度，将在线问题离线化分治的递归过程用于解决段内问题，两段间问题由分治主过程解决在特殊场合有很好的效果优势：代码简短易读，效率不错劣势：递归过程导致常数变大，有时候需要去递归（能够代替树套树这种数据结构的还有可持久化数据结构，有兴趣的同学可以去研究下。）2022-5-217474FJOI2012 POINT原题目较长，剔除边界情况后抽象成下列问题：有长度为N的数组，开始时是空的。执行N个操作Pi Qi，表示在第Pi位填上Qi。Pi,Qi是1到n的排列。每个操作之后，输出序列的逆序对个数。n=50000用树套树、块状链表或者今天讲的分治方法，很容易做到O(nlog2n)或相近的复杂度。考场上前两者都只拿到了50分。有没有低于O(nlog2n)的方法？比如O(nlogn)？2022-5-217575
