数据结构题的非经典解法——整体二分与CDQ分治

>仅适用于允许离线的题目（但是存心想考数据结构的出题人怎么会给你这个机会）

<h1 style="font-family:times">CDQ分治</h1>
陈丹琪在论文中讲述的关于$cash$这一类的问题的解法。
当然其实我没有从她的论文里面看出什么就是了（并没有找到论文原文）
****
当你树套树打烦了搞基数据结构码得快要死了，如果题目允许如果出题人不那么如xcc一般的jay，设计这造化的神犇还稍有仅使留下的以淡红的血色换来的微末的良心给你以苟且偷生，你就可以试着以CDQ（或是整体二分）来为这世界写一点东西——你觉着早有写它的必要了。
****
一般遇到的分治是对静态区间或是静态具有相似结构且互不影响的问题所做的分开处理然后拼起来。这里就有三个限制条件：静态，相似子结构，以及互不影响。

但是一般的数据结构题都有三个特征：动态，不相似的子结构，以及互相影响。
****
那么CDQ分治是如何做到代替一些数据结构的呢？

我们一般进行的分治都是对一个序列、一段区间或是一个数分治，这些都可以形象地称为“对空间所做的分治”，因为对于代码来说这些就是具体的空间里的东西。

对于数据结构题来说，空间（即序列或是一棵树上维护的东西）显然是不对称的。但是我们注意到，操作显然是相似的。（废话）

这也正是CDQ分治不同于其它分治的地方——一般所用分治的对象是区间或者答案，基于空间。而CDQ分治是基于时间的对象是操作的分治。这也就是它必须做为离线算法的缘故。

当然CDQ之前（或者CDQ之时）有必要按照某一维关键字排序，使这一维关键字的影响常数化，不然这就跟暴力没什么区别了。

****
由于时间显然单调，所以可以每次将时间（也就是操作）分为[l,mid]和[mid+1,r]，但是这样就面临了一个问题：[mid+1,r]对[l,mid]是不会有影响的，所以[l,mid]可以单独计算，但是[l,mid]对[mid+1,r]也许是有贡献的，所以不能单独处理。

于是采取一个亦可赛艇的措施：暴力统计[l,mid]对[mid+1,r]的贡献，然后为了避免影响到后续的分治，再暴力修改回来。

这里需要注明一下，就是我们所求的答案其实就是原序列原本的答案+操作对答案的贡献，也就是影响。每次递归的时候，在此次处理之前的所有贡献都相当于变成了“原本的答案”，已经加到了ans里面，这些贡献与其它的贡献是不相关的，会稳定在此处不变。
其实这也规定了CDQ分治的使用范围。但无论如何满足上述条件时，我们只需要计算当前左区间对右区间的贡献，无需理会整个序列。所以相应的，此层递归结束时，我们又要使序列回到原本的样子，因为这里的贡献只能计算一次。

就是$\uparrow$这一步使得CDQ分治解决了最后一个“互不影响”的限制，这样我们就可以对一些问题离线后进行CDQ分治了。

而CDQ分治的优秀之处也就在于此：在一般的数据结构一样容易理解（甚至比一些数据结构比如后缀三姐更加易懂）的情况下，将码量从inf减到不超过五十行。
****
可以看出，CDQ分治最多递归$log_2n$层，其中为每层处理的复杂度设为$f(C)$，那么总复杂度就是$\Theta(n*f(C))$，一般情况下$f(C)$是$\Theta(n)$或者$\Theta(n*log_2n)$，总体来说是很优秀的复杂度。

就像对NOI2007Cash一题，我们用CDQ维护时，先递归处理[l,mid]，再计算左边对右边的影响，并且操作回退以免贡献重复计算，最后递归统计[mid+1,r]，并且不要忘记了数组始终要保持一维关键字有序：
```cpp
bool operator< (func &a,func &b) {return a.x==b.x?a.y<b.y:a.x<b.x;}
bool cmp(const int &a,const int &b) {return p[a].k>p[b].k;}
void CDQ(int l,int r,D last) {
	if(l==r) {
		ans[l]=max(ans[l],last);
		f[l].y=ans[l]/(p[l].a*p[l].r+p[l].b);
		f[l].x=f[l].y*p[l].r;
		return;
	}
	int mid=l+r>>1,t1=l,t2=mid+1,t=0,h=0;
	for(int i=l;i<=r;++i)
		if(id[i]<=mid) s[t1++]=id[i];
		else s[t2++]=id[i];
	memcpy(id+l,s+l,sizeof(int)*(r-l+1));
	CDQ(l,mid,last);
	for(int i=l;i<=mid;v[t++]=f[i++]) for(;t&&cross(v[t-2],v[t-1],f[i])>=0;) --t;
	for(int i=mid+1;i<=r;++i) {
		for(;h<t-1&&calc(v[h],id[i])<calc(v[h+1],id[i]);) ++h;
		ans[id[i]]=max(ans[id[i]],calc(v[h],id[i]));
	}
	CDQ(mid+1,r,ans[mid]);
	merge(f+l,f+mid+1,f+mid+1,f+r+1,v);
	memcpy(f+l,v,sizeof(func)*(r-l+1));
}
```
****
<h1 style="font-family:times">整体二分</h1>
论文原文粘贴：
![图片标题](https://leanote.com/api/file/getImage?fileId=5a55a567ab644102a4001774)
对贡献的阐述同时也适用于CDQ分治。
论文比任何人讲得都通俗易懂多了。这里就只给出bzoj1901的代码实现:
```cpp
int get(int o) {int ans=0;for(;o;o-=o&-o) ans+=c[o];return ans;}
void add(int o,int v) {for(;o<=n;o+=o&-o) c[o]+=v;}
bool part(qes &a) {
	if(a.op==3) {
		if(a.w+a.add>a.k-1) return 1;
		a.w+=a.add,a.add=0;return 0;
	} else return a.y<=now;
}
void divide(int lef,int rig,int l,int r) {
	if(lef>rig) return;
	if(l==r) {
		for(register int i=lef;i<=rig;++i)
			if(q[i].op==3) ans[q[i].id]=l;
		return;
	}
	int mid=l+r>>1;now=mid;
	for(register int i=lef;i<=rig;++i) {
		if(q[i].op==1&&q[i].y<=mid) add(q[i].x,1);
		if(q[i].op==2&&q[i].y<=mid) add(q[i].x,-1);
		if(q[i].op==3) q[i].add=get(q[i].y)-get(q[i].x-1);
	}
	for(register int i=lef;i<=rig;++i) {
		if(q[i].op==1&&q[i].y<=mid) add(q[i].x,-1);
		if(q[i].op==2&&q[i].y<=mid) add(q[i].x,1);
	}
	int dv=stable_partition(q+lef,q+rig+1,part)-q-1
	divide(lef,dv,l,mid);
	divide(dv+1,rig,mid+1,r);
}
```

Annoyrain

导航

最近发表

友情链接