[学习笔记] CDQ分治&整体二分

突然诈尸.png

这两个东西好像都是离线骗分大法...

不过其实这两个东西并不是一样的...

虽然代码长得比较像

CDQ分治

基本思想

其实CDQ分治的基本思想挺简单的...

大概思路就是长这样的:

1. 程序得到一个有序的操作/查询序列$[l,r)$ (于是就不能在线了QAQ)
2. 将这些操作分成两部分$[l,mid)$和$[mid,r)$递归下去处理. 显然直接分下去一定还是有序的于是我们不用管它
3. 计算$[l,mid)$中的操作对$[mid,r)$的查询的贡献. 也就是用左半部分的子问题辅助解决右半部分的子问题

和普通分治的区别其实就在于普通分治不会让$[l,mid)$对$[mid,r)$产生贡献

个人感觉左闭右开写起来比较方便还能减少奇奇怪怪的$\pm 1$计算

不过有一点需要注意, 根据主定理, 为了保证复杂度, 计算贡献的过程的时间复杂度必须只和当前分治区间长度有关, 如果和总长有关的话就GG了...

正确性

其实这个CDQ的过程就像线段树分治

我们考虑CDQ分治中产生的分治线段树. 由于这是个树所以每对叶子结点(操作/查询)都有一个唯一的LCA. 而一个叶子对$(o,q)$会对最终输出答案产生影响, 当且仅当$o$是一个操作且$o$在LCA的左子树, $q$是一个查询且$q$在LCA的右子树. 所以每一对贡献我们只会在LCA处计算一次, 正确性得证.

当然上述过程要基于贡献的可加性 (即相关运算满足交换律/结合律, 如$\min$, $\max$, $+$, $\oplus$...啥的)

裸的应用举例

二维偏序

为啥先讲二维偏序呢?

因为讲了3维偏序之后就没了

裆燃是让大家一步一步理解辣~(一本正经地胡说八道中)

回忆一下归并排序求逆序对的过程, 我们在合并两个子区间的时候, 要考虑到左边区间的对右边区间的影响. 即, 我们每次从右边区间的有序序列中取出一个元素的时候, 要把"以这个元素结尾的逆序对的个数"加上"左边区间有多少个元素比他大". 其实这是一个典型的CDQ分治的过程.

现在我们把这个问题拓展到二维偏序问题. 在归并排序求逆序对的过程中, 每个元素可以用一个有序对$(a,b)$表示, 其中a表示数组中的位置, b表示该位置对应的值. 我们求的就是"对于每个有序对$(a,b)$, 有多少个有序对$(a',b')$满足$a'<a$且$b'>b$ ", 这就是一个二维偏序问题.

注意到一开始我们默认$a$是有序的, 于是我们可以直接忽略$a$带来的影响而计算, 因为$[l,mid)$区间中的所有$a$均要小于$[mid,r)$区间内的所有$a$. 其实我们可以理解为"这一维被CDQ分治掉了"

二维偏序Ex

考虑这么一个问题:

给定一个$n$个元素的序列$a$, 初始值全部为$0$, 对这个序列进行以下两种操作: 操作1: 格式为1 x k,把位置$x$的元素加上$k$ (位置从$1$标号到$n$). 操作2: 格式为2 x y,求出区间$[x,y]$内所有元素的和.

大家肯定会想"啊这不树状数组沙比提嘛看我$5\texttt{min}$就切掉"

然而我们为了教学就是要没事找事用CDQ来写

显然我们可以把它转化为二维偏序问题, 第一维为操作时间, 第二维表示操作位置, 贡献就是加和.

于是我们就可以按照离线题的套路定义一个结构Event表示广义操作(或者事件), 把类型($0/1$, 代表这是操作还是查询)/各个维度信息/贡献相关信息都存进去, 按照维度信息排好序就可以了

这题里面因为第一维是操作时间所以按顺序构造出来之后不用排序就可以直接上CDQ

太简单了不放代码了

三维偏序

其实我们会发现普通的联赛数据结构(树状数组/线段树)完全就能解决二维偏序问题, 完全用不上CDQ分治

然而三维就比较GG了

一般操作是树套树来解决这个问题(其实也相当于是"一层解决一维")

然而当你遇到了如下情况:

• 时间不多了不够写树套树/k-D树了
• 偏序关系限制下的的贡献很复杂
• 题目本身并没有强制在线/题目需要求贡献总和

你就需要CDQ分治了

然后我们来看最基本的题目: 三维偏序(多数CDQ问题都是转化为三维偏序之后解决的)

有$n$个元素, 每个元素有 $(a_i,b_i,c_i)$ 三个属性, 设 $f(i)$ 表示满足 $a_i \leq a_j$, $b_i\leq b_j$, $c_i\leq c_j$ 的 $j$ 的数量.

对于 $d \in [0,n)$, 求满足 $f(i)=d$ 的 $i$ 的数量

在这道题目中, 我们其实完全可以将操作和查询合并, 每个Event既是操作又是查询.

我们类似二维偏序, 首先把按照第一维排序把它CDQ掉, 然后我们就可以专注于 $b$ 和 $c$ 两维产生的贡献了

接着我们按照 $b$ 元素升序归并排序 (降常数用的...用std::sort也没人拦你) , 这样我们就在归并的过程中处理掉了$b$ 维的偏序 (归并过程中先访问的会对后访问的产生影响, 因为你排序了). 最后剩下 $c$ 维的偏序, 我们就可以使用一些普通数据结构 (比如树状数组) 来解决了.

需要注意的一点是当前CDQ部分执行完后要把树状数组清空, 而且不能使用 $O(n)$ 的清空方法, 需要懒惰删除来保证复杂度.

具体实现:

void CDQ(int l,int r){
    if(r-l==)
        return;
    int mid=(l+r)>>;
    CDQ(l,mid);
    CDQ(mid,r);
    int lp=l,rp=mid,p=l;
    while(lp<mid||rp<r){
        if(lp<mid&&rp<r){
            if(N[lp].b<=N[rp].b){
                Add(N[lp].c,N[lp].w);
                buf[p++]=N[lp++];
            }
            else{
                N[rp].cnt+=Query(N[rp].c);
                buf[p++]=N[rp++];
            }
        }
        else if(lp<mid){
            Add(N[lp].c,N[lp].w);
            buf[p++]=N[lp++];
        }
        else{
            N[rp].cnt+=Query(N[rp].c);
            buf[p++]=N[rp++];
        }
    }
    for(int i=l;i<mid;i++)
        Add(N[i].c,-N[i].w);
    for(int i=l;i<r;i++)
        N[i]=buf[i];
}

因为带重而且条件还是 $\leq$ 所以就去重然后把对应个数放在N[i].w里了

非常容易理解(吧)

时间复杂度的话, 递归式是 $T(n)=2T(n/2)+O(n\log(n))$, 解出来是 $O(n\log^2(n))$ 的级别.

三维偏序Ex

考虑一个二维树状数组题:

平面上有 $n$ 个点，要求 $q$ 个询问，每个询问为查询在指定矩形 $(x_1,y_1)$ 到 $(x_2,y_2)$ 的矩形之间有多少个点

煞笔二维前缀和?

然而...

$x,y \in [1,1\times 10^7]$, $n,q \leq 1\times 10^5$

等等我们是不是可以离散化一下呢?

然而每一维还是需要至少 $1\times 10^5$ 个点, 依然GG

于是人群中钻出一个k-D TreeCDQ分治

首先我们按照二维树状数组解法的套路把一个查询拆成四个来差分求和

接着我们就非常偷税地发现我们只要求个二维前缀和就星了

实际上就相当于 $(t,x,y)$ 三维偏序, 贡献为求和

直接套刚刚的板板就星了

然而拿来写简单题会MLE...这可真蠢...

正确板板题链接->园丁的烦恼 Mokia

不裸的应用举例

天使玩偶

题意: 动态插入一些坐标系上的点, 要求查询这些插入的点到到指定查询点的曼哈顿距离的最小值

一道k-D Tree裸题

曼哈顿距离的表达式是长这样的:

$$ dis(A,B)=|A_x-B_x|+|A_y-B_y| $$

因为带绝对值, 我们按照套路把绝对值拆开成$4$种情况来计算

这样的话我们相当于翻转$4$次坐标系后计算下面这个式子的最小值:

$$ans(A)=\min\{A_x - B_x + A_y - B_y | B_x \leq A_x , B_y \leq A_y, B_t\leq A_t \}$$

其中$A_t$为插入/查询时间, 问题转化为一个三维偏序问题, 计算满足偏序关系的点的$B_x+B_y$的最大值. 可以用CDQ分治和树状数组来解决.

不过翻转坐标系之后的偏序关系是完全一样的, 所以可以只写一个CDQ函数然后在外面翻转.

在这个题目中, 贡献就变成了曼哈顿距离最小值

并不能折叠代码于是就不在这里贴实现了

因为复杂度是严格两个 $\log$ 于是跑得并不如玄学复杂度的 k-D Tree 快...另一道题直接就TLE了...

动态逆序对

题意: 给定一个排列, 动态删除其中的一些数字, 每次删除之前输出当前序列的逆序对数量

一道树套树裸题

我们首先把操作离线成倒序插入, 每次求出插入一个数字后的逆序对数量

然后把插入时间, 插入位置和插入的值 $(t,p,v)$ 做三维偏序, 每次求出插入当前值时贡献的逆序对数量

发现 $t$ 的偏序关系都是 $t<t'$ 时对 $t'$ 有贡献, 但 $p$ 和 $v$ 就要分成两类:

• $p < p'$ 且 $v>v'$
• $p>p'$ 且 $v<v'$

咋办呢?

两遍CDQ呗

当然同样可以写在一个函数里...然而好像比较容易翻炸...乖乖写两个好了...

或者...

void CDQ(int l,int r){
	if(r-l==1)
		return;
	int mid=(l+r)>>1;
	CDQ(l,mid);
	CDQ(mid,r);
	{
		int lp=l,rp=mid,p=l;
		while(lp<mid&&rp<r){
			if(A[lp].p>A[rp].p){
				Add(A[lp].v,1);
				T[p++]=A[lp++];
			}
			else{
				ans[A[rp].t]+=Query(A[rp].v);
				T[p++]=A[rp++];
			}
		}
		while(lp<mid){
			Add(A[lp].v,1);
			T[p++]=A[lp++];
		}
		while(rp<r){
			ans[A[rp].t]+=Query(A[rp].v);
			T[p++]=A[rp++];
		}
		for(int i=l;i<mid;i++)
			Add(A[i].v,-1);
		for(int i=l;i<r;i++)
			A[i]=T[i];
	}
	{
		int lp=l,rp=mid,p=l;
		while(lp<mid&&rp<r){
			if(B[lp].p<B[rp].p){
				Add(n+1-B[lp].v,1);
				T[p++]=B[lp++];
			}
			else{
				ans[B[rp].t]+=Query(n+1-B[rp].v);
				T[p++]=B[rp++];
			}
		}
		while(lp<mid){
			Add(n+1-B[lp].v,1);
			T[p++]=B[lp++];
		}
		while(rp<r){
			ans[B[rp].t]+=Query(n+1-B[rp].v);
			T[p++]=B[rp++];
		}
		for(int i=l;i<mid;i++)
			Add(n+1-B[i].v,-1);
		for(int i=l;i<r;i++)
			B[i]=T[i];
	}
}

高端应用举例

下面的都是些高端操作...

因为阿克业突然咕咕咕于是ddl缠身的rvalue只是嘴了嘴做法而并没有亲自去完整实现...

趁早赶出来趁早搞完好了(咕咕咕

城市建设

题意: 给定一张无向图, 要求支持修改边权操作并在每次修改边权之后求出当前最小生成树大小

其实感觉这题只是普通分治而不是CDQ...然而思路比较清奇而且被老姚打了CDQ标签就放出来好了

直观思路是当分治到叶子的时候求一下当前的最小生成树

然后上层非叶子结点的时候要做两个操作:

• construction求出所有一定在最小生成树中的边并加入答案并缩边, 之后不再考虑. 计算方法是将所有当前区间修改掉的边都加入最小生成树后再求最小生成树. 正确性显然.
• reduction 求出所有不可能加入最小生成树的边, 直接扔掉. 计算方法是禁止加入当前区间修改掉的边然后尽量求最小生成树, 此时扔掉的边就可以彻底扔掉了

进行这两个操作后图的规模好像会缩小很多...

具体缩小多少好像并没有找到证明...

复杂度是O(玄学)...

货币兑换

并不存在一句话题意(看原题吧)

感觉这个是最高端的操作了

首先每天一定只有两种决策, 要么买买买, 要么卖卖卖 (有利可图显然多多益善, 可能亏损显然一点都不碰是最优的)

那么设 $f(i)$ 为前 $i$ 天的最大收益, $a_i$ 为第 $i$ 天全部买入时能得到的A券数目, $b_i$ 同理

则 $a_i =\frac{R_jf(j)}{R_jA_j+B_j}$, $b_i=\frac{f(j)}{R_jA_j+B_j}$. 如果在第 $i$ 天将第 $j$ 天买入的金券全部卖出, 则得到的价值是$A_ia_j+B_ib_j$

于是 $f(i)=\max\{f(i-1),A_ia_j+B_ib_j\}$.

于是直接就变成斜率优化了...因为显然只有上凸壳上的 $(a_i,b_i)$ 才有可能做出贡献

然而并不能直接斜率优化...因为这斜率™并不是单调的

标准做法是用平衡树维护上凸壳并在查询的时候二分

hzoi2017_jjm: 啊Treap维护上凸壳不是很好写的么...我写过啊

rvalue: orz!

显然大家都没有hzoi2017_jjm强, 所以我们选择更加好用的CDQ分治来写这个题.

首先我们发现最大的问题在于决策点式中的 $a_j, b_j$ 与 $f(j)$ 有关, 所以我们必须要在 $f(j)$ 完全计算完成的情况下计算它对后面的贡献. 于是我们调整CDQ分治顺序, 先递归 $[l,mid)$ 将它完全计算完成.

接着对于当前CDQ分治区间 $[l,r)$:

因为 $[l,mid)$ 区间内的 $f(i)$ 均已计算完成, 我们将其中的决策点的上凸壳求出来. 然后将 $[mid,r)$ 区间内的点按斜率排序强行让斜率单调, 最后扫一遍即可得到 $[l,mid)$ 区间对 $[mid,r)$ 区间内的斜率能产生的最大贡献.

一直维护下去就好了...不过据说快排会T掉...还是老老实实归并排序吧

整体二分

基本思想

整体二分主要是把所有查询放在一起二分答案, 然后把操作也一起分治.

对没错, 放在一起. 计算的时候扫一遍当前处理的区间, 把答案在 $[l,mid)$ 的查询放在一边递归下去, $[mid,r)$ 的放在另一边递归下去, 递归到叶子就有答案了.

其实有点像是二分在数据结构题目上的扩展, 因为数据结构题一般不仅有多组查询还有其他的修改...

特征性质

• 查询具有可二分性
• 操作对判定结果的贡献相互独立(前面操作对后面操作的贡献有不同影响的话会当场去世)
• 如果操作对答案判定有影响, 则这个贡献是一个确定的与判定标准无关的值
• 贡献满足可加性(交换律/结合律)
• 没有强制在线

应用举例

动态排名系统

题意: 给定一个序列, 支持单点修改和查询区间 $k$ 小.

一道煮席树裸题

不过如果内存开64MB的话主席树就不可做了

首先我们发现这个答案肯定是有可二分性的

其次我们要二分的判定依据就是指定询问区间中小于当前值的值的个数.

然后我们把所有值根据与当前二分的值域的 $mid$ 的比较结果转化成 $0/1$ , 问题就变成了一个单点修改区间求和过程, 按照套路使用树状数组即可解决.

我们发现一个值大于 $mid$ 的修改对于被判定为小于 $mid$ 的查询不会再产生任何贡献 (贡献是确定值的用处) , 于是我们把这些修改划分到另一边. 一个值小于 $mid$ 的修改对于被判定为大于 $mid$ 的查询一定会一直产生贡献, 我们把它产生的贡献累加到后面的查询上 (贡献满足可加性的用处) 然后就可以把这些修改划分到另一边了.

而对答案造成影响的修改, 判定答案减小后仍可能造成影响. 所以我们将它们和对应的查询划到一起

划分的时候因为是反归并的过程所以一直保持着时间顺序, 所以直接一边跑修改一边查询问就星了

核心过程代码:

全局数组: int ans, int cnt, Event q, Event tmp, bool left

void Solve(int l,int r,int L,int R){
    if(R-L==){
        for(int i=l;i<r;i++){
            if(q[i].op==)
                ans[q[i].id]=L;
        }
        return;
    }
    int mid=(L+R)>>;
    for(int i=l;i<r;i++){
        if(q[i].op==)
            cnt[i]=Query(q[i].r)-Query(q[i].l-);
        else if(q[i].v<=mid)
            Add(q[i].pos,q[i].op);
    }
    int lcnt=;
    for(int i=l;i<r;i++){
        if(q[i].op==){
            if(q[i].cur+cnt[i]>=q[i].v){
                left[i]=true;
                ++lcnt;
            }
            else{
                left[i]=false;
                q[i].cur+=cnt[i];
            }
        }
        else{
            if(q[i].v<=mid){
                left[i]=true;
                ++lcnt;
            }
            else
                left[i]=false;
        }
    }
    for(int i=l;i<r;i++)
        if(q[i].op!=&&q[i].v<=mid)
            Add(q[i].pos,-q[i].op);
    int lp=l,rp=l+lcnt;
    for(int i=l;i<r;i++){
        if(left[i])
            tmp[lp++]=q[i];
        else
            tmp[rp++]=q[i];
    }
    for(int i=l;i<r;i++)
        q[i]=tmp[i];
    Solve(l,lp,L,mid);
    Solve(lp,rp,mid,R);
}

(以上代码由于时间紧迫未经测试...但是和网上代码对比并没有很大差异于是我们假装它是对的)

时间复杂度分析和三维偏序一样

Meteors

题意: 给定一坨区间加的操作, 每个点都属于一个点集, 而每个点集有一个需求量, 对于每个点集求什么时候集合内的点的当前值之和达到需求量

显然到达时间是可以二分的.

于是整体过程就变成了: 把第 $[l,mid)$ 区间内的修改全都执行掉, 然后判断当前点集是否满足要求. 若满足要求则分在 $[l,mid)$ 一侧, 否则将已经做出的贡献累加并分到 $[mid,r)$ 一侧.

而这个修改和查询的过程就是区间修改单点查询, 按照套路使用树状数组前缀和即可解决.

然后套刚刚那题的板板就可以辣~