(Day1)cdq分治相关

专题讨论：分治方法AC_Aerolight2013.4.28~2013.4.29@FuzhouPREFACE今天首先讨论的是一种特殊的分治方法，在OI界初见于陈丹琦2008年的集训队作业中，因此也被称为CDQ分治。随后将讨论一些利用了分治思想的其他算法。这节课的目的是科普，因此题目会较简单，讲解也会比较详细。如果对该算法或对特定问题已有深入了解可以跳过不听，但不要打扰其他同学。Let’sbegin.PREFACE先看几个常见的递归复杂度分析。T(n)=2T(n/2)+O(kn)的解是T(n)=O(knlogn)MasterTheoremT(n)=2T(n/2)+O(knlogn)的解是T(n)=O(knlog^2n)T(n)=2T(n/2)+O(k)的解是T(n)=O(kn)一棵N个节点的线段树上有几个节点？K是一个和N无关的多项式INTRO：归并排序给定排列P，求排列的逆序对数量。P的长度=100000。要求O(nlogn)定义归并排序过程Merge(l,r)Merge(l,r)Merge(l,mid)Merge(mid+1,r)Count(l,mid,mid+1,r)只需要考虑左右两段之间造成的逆序对，段内的逆序对由递归解决[NOI2007]CASH有两种金券，金券按比例交易：买入时，将投入的资金，购买比例为Rate[i]的两种金券；卖出时，卖出持有的一定比例的金券。已知未来n天两种的金券价格A[i]、B[i]，初始资金为s，求最大获利。为使获利最大，交易时显然应该全部买进或卖出。1=n=100000[NOI2007]CASH简要做法：令F[i]表示第i天获得的最大B卷数量。枚举上一次交易日jF[i]=max{ans,Rate[j]*F[j]*A[i]+F[j]*B[i]}/(rate[i]*a[i]+b[i])O(n^2)观察括号内的表达式，可以发现决策J优于决策K的条件：(rate[j]*f[j]-rate[k]*f[k])/(f[j]-f[k])-b[i]/a[i]上面这个式子的左边，一般记成slope(j,k)[NOI2007]CASHSlope(j,k)-b[i]/a[i]令G[i]=rate[i]*f[i]，在二维平面上定义点Xi=(Fi,Gi)Slope(j,k)就是通过Xj和Xk的斜率维护一个点集X，支持以下两个操作：1)在第一象限的任意位置插入一个点2)给定负数斜率K，求所有斜率为K且过点集中任意点的直线在Y轴上的最大截距操作2最终用到的点都会在点集的上凸壳上维护点集X的凸包，支持动态插入和斜率查询平衡树结构O(nlogn)[NOI2007]CASH算法存在的问题边界情况众多难写难调观察操作2中，提供的斜率值是-bi/ai，可以预处理得到而和F的取值无关这意味着在插入节点Xi时，已经可以确认它对询问j(ji)带来的影响引入分治思想[NOI2007]CASH定义过程Solve(L,R)假设运行Solve(l,r)可以得到F[l]到F[r]的值。[L,mid]区间里的询问，可以直接递归Solve(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)[NOI2007]CASH整体考虑[l,mid]对[mid+1,r]的影响给定点集X和一系列询问每个询问是一个负数斜率回答所有斜率符合且通过点集X中任意点的直线中，Y轴的最大截距是多少只要考虑点集X的上凸包。对于每个询问，在凸包上二分即可。这一步的复杂度是O(nlogn)，这里n=r-l。[NOI2007]CASH时间复杂度？Solve(l,r)的复杂度是O(nlogn)T(n)=2T(n/2)+O(nlogn)T(n)=O(nlog^2n)离最优化还有距离。需要logn的地方1)求点集凸包2)二分答案[NOI2007]CASH1)点集凸壳合并两个凸壳的时间复杂度是O(n+m)Solve(l,r)结束后返回[Xl..Xr]的凸壳单步O(n)，总体O(nlogn)2)二分答案放弃二分，离线处理把点集凸壳和所有询问排序，用两个指针扫描2’)对询问排序提前对询问进行一次归并排序，存储所有中间结果为什么不能在Solve()时进行归并？预处理复杂度O(nlogn),主递归中单步O(n)T(n)=2T(n/2)+O(n),T(n)=O(nlogn)[NOI2007]CASHSolve(l,r)是递归函数如何消除递归？手工栈模拟递归存储中间过程？T(n)的解不变，但常数减小。总结1)分治思想-只考虑跨立作用2)段内影响忽略不计-问题离线化[WF2011]MACHINEWORKS你的公司获得了一个厂房N天的使用权和一笔启动资金，你打算在这N天里租借机器进行生产来获得收益。可以租借的机器有M台。每台机器有四个参数D,P,R,G。你可以在第D天花费P的费用（当然，前提是你有至少P元）租借这台机器，从第D+1天起，操作机器将为你产生每天G的收益。在你不再需要机器时，可以将机器卖掉，一次性获得R的收益。厂房里只能停留一台机器。不能在购买和卖出机器的那天操作机器，但是可以在同一天卖掉一台机器再买入一台。在第N+1天，你必须卖掉手上的机器。求第N+1天后能获得的最大资金。[WF2011]MACHINEWORKS数据范围租借天数D=10^9初始资金C=10^9机器数N=10^5对于每个机器：租借日Di=D买入价Pi和卖出价Ri满足1=RiPi=10^9每日收益Gi满足1=Gi=10^9[WF2011]MACHINEWORKS观察场地能放机器就一定要放么？先将机器按照出售时间Di排序。将所有时间离散化。用Fi表示在时刻Di卖掉手上机器后最多剩下多少钱。Fi=Max(F[i-1],F[j]-P[j]+R[j]+G[j]*(D[i]-D[j]-1))条件是F[j]P[j]。O(n^2)[WF2011]MACHINEWORKSFi=Max(F[i-1],F[j]-P[j]+R[j]+G[j]*(D[i]-D[j]-1))F[j]P[j]令A[j]=F[j]-P[j]+R[j]-G[j]*D[j]-G[j]那么F[i]=Max(F[i-1],A[j]+G[j]*D[i])和上一题一样了。注意到斜率D[i]是不变的，因此可以对整个[F1,Fn]进行分治。复杂度O(nlogn)，和平衡树维护凸壳同阶[WF2011]MACHINEWORKSF[i]=Max(F[i-1],A[j]+G[j]*D[i])在平面上有若干直线y=G[j]*x+A[j]维护一个直线集，支持以下两类操作插入一次函数y=kx+b给定询问D，求所有函数在x=d上的最大值维护一系列半平面交对偶问题？[BOI2007]MOKIA有一个2000000*2000000的棋盘，每个格子上有一个数字A[x,y]，现在要执行两类操作：Addxya：A[x,y]+=aQueryx0y0x1y1：询问矩阵(x0,y0)-(x1,y1)内所有格子的数字和。Add操作数=160000Query操作数=10000[BOI2007]MOKIA棋盘大小和询问数相差巨大，所以肯定要离散化。二维线段树维护？MLE+TLE二维树状数组+Hash？Hash常数过大空间怎么开？？[BOI2007]MOKIA和之前的想法类似，定义操作Solve(L,R)Solve(L,R)应当能够处理[L,R]之间的所有操作Solve(L,R)Solve(l,mid)处理[l,mid]中操作对[mid+1,r]中操作的影响Solve(mid+1,r)如何处理？[BOI2007]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(nlog^2n)[VIOLET3]天使玩偶维护二维点集P，支持以下两个操作(1)插入点(x,y)(2)给定询问(x,y)，求点集中离询问点最近的点距离定义为曼哈顿距离Dis(P1,P2)=|x1-x2|+|y1-y2|N,m=300000X,y=1000000k-d树能不能做[VIOLET3]天使玩偶去除Dis(P1,P2)的绝对值符号分4种情况讨论：左上，左下，右上，右下只需要考虑一种情况（答案在询问的左下）维护点集P，支持以下操作(1)将(x,y)插入点集(2)给定询问(x,y)，求满足dis(p1,p2)=(x-x’)+(y-y’)=x+y-(x’+y’)最小的点问题转为求x’+y’最大的点没有操作1的情况对x排序，对y维护树状数组[VIOLET3]天使玩偶定义操作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,y’=y的最小x’+y’。退化为没有操作1的情况按X排序，对Y维护树状数组T(n)=2T(n/2)+O(nlogn),T(n)=O(nlog^2n)2DPARTIALORDER有N个人，每个人有两种能力值Pi,Qi。如果PiPj&&QiQj，称I比J有能力现在要求出最长的一个序列A=(A1,A2,…,At)，满足Ai比Ai+1有能力N=100000。为了简单起见，P和Q都是1到N的排列。把人按照Pi排序，问题变为求序列Qi的LISF[i]=Max({F[j]|ji&&Q[j]Q[i])+1用数据结构维护，做到O(nlogn).3DPARTIALORDER有N个人，每个人有三种能力值Pi,Qi,Ri。如果PiPj&&QiQj&&RiRj，称I比J有能力现在要求出最长的一个序列A=(A1,A2,…,At)，满足Ai比Ai+1有能力N=40000。为了简单起见，P,Q,R都是1到n的排列3DPARTIALORDER首先可以按照Pi把人排个序。现在要求的是满足ij,QiQj,RiRj的最长序列。用F[i]表示以第i个人结尾的最长序列F[i]=Max{F[j]|ji,QjQi,RjRi}+1怎么搞？线段树套平衡树/可持久化线段树O(nlog^2n)3DPARTIALORDER尝试在这个问题上进行分治。定义过程Solve(l,r)，能够得到F[l]..F[r]的值Solve(l,r)Solve(l,mid)处理[l,mid]中元素对[mid+1,r]中F[x]取值的影响Solve(mid+1,r)F[x]=Max{F[j]|jx,QjQx,RjRx}+11)x在[l,mid]中：集体处理2)x在[mid+1,r]中：由递归解决3DPARTIALORDER处理[l,mid]中元素对[mid+1,r]中F[x]取值的影响维护带权点集X=(Qi,Ri)(l=i=mid)，权值F[i]支持询问：给定点(Qj,Rj)(mid+1=j=r)在点集X中寻找一个点(Qi,Ri)使得QiQj且RiRj，满足以上条件的点中