2017-07-25

CDQ学习笔记

CDQ 分治学习笔记

学习的目的

在任何一个OIer的职业生涯中，都会碰到一些繁琐的数据结构题，而现在的省选有基本是数据结构大战，可见数据结构的重要性，但是和我说的CDQ有什么关系QAQ？？？
数据结构写起来，基本上就呵呵了，动不动两三百行的代码，调试时基本万念俱灰。。。（可能是我比较菜QAQ）
这个时候CDQ的用处就很明显的，写起来简单，写起来简单，写起来简单！！！

算法要求与使用

大前提:

CDQ一定是处理离线算法，如果强制在线，还是要么暴力，要么刚数据结构。

使用：

1.区间维护什么的就乱搞了，其实也用不到CDQ，但我们要清楚，区间维护其实就是维护一个二维偏序，具体做法我们稍后再说。
2.CDQ的真正用处在于维护一个三维偏序，一般的做法是套用一个树状数组维护第三维。三维偏序的理解，举个例子给你很多三维坐标如(a,b,c),希望你求坐标满足:
a<x&&b<y&&c<z的点的个数有多少个；

具体实现

很多前辈都说CDQ的写法与归并排序超级像，其实也真的是超级像。
先说一下二维的实现：
如果给你一个区间，有很多点权值，支持单点修改和区间查询。其实树状数组乱秒，考虑CDQ怎么做。
对于每个操作我们必须要维护一个时间序，否则会乱套。那么考虑这么一个事实，每次修改操作一定是对后面发生的询问有影响，而我们已经将操作们按照时间排了序，分治的模型可能就出来了吧QAQ。我们递归枚举左区间和右区间，只是在合并前要多一步，考虑左区间中元素对右区间的影响：
记操作的区间的左端点是x，右端点是y;那么满足
q[i].x<q[j].x
都会对查询有影响，注意我们查询的是两个前缀和：sum[x-1],sum[y];那么我们很清楚查询到x-1时，对这次区间询问的答案应该是减去sum[x-1]的，而到y时，便是加上sum[y]。
好了可以总结一下，CDQ的基本思路就是保证左区间与右区间的修改和查询独立协调后，处理左区间对右区间的影响。
如果左区间的所有元素都不满足于修改条件（见上），那么说明右区间的查询部分是不受限制的，可以直接更新答案。
好了差不多就这样了，如果还是不清楚的话，可以在看几篇博客，知识点不可能看一篇文章就能学会的。

三维偏序

三维偏序其实是对二位偏序的拓展。
我们可以保证默认序时间序是有序的，我们也能保证第二维在维护的时候可以有序，但是第三维我们只能放弃，否则会冲突。这时候我们可以借助一个简单的数据结构，比如说树状数组来维护。

先放一道入门题

比模板题多一点点操作在于只用容斥把查询稍微转化一下就行了

因为有些查询是对答案有利，有些不是，所以定义的时候可以应入一个w变量=1||-1来记录状态。
贴一波同组写的题解

传送门

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define lowbit(x) (x&(-x))
using namespace std;
int s,w,sz[2000100];
struct node{
	int type,x,y,num,w;
	node(int _type=0,int _x=0,int _y=0,int _num=0,int _w=0){
		type=_type,x=_x,y=_y,num=_num,w=_w;
	}
	friend bool operator  <= (node a,node b){
		return a.x<=b.x;
	}
}q[500500],tmp[2000100];int cnt,tot,ans[100010];
void update(int x,int y){
	for(int i=x;i<=w;i+=lowbit(i))
		sz[i]+=y;
}
int query(int x){
	int rtn=0;
	for(int i=x;i;i-=lowbit(i))
		rtn+=sz[i];
	return rtn;
}
void CDQ(int l,int r)
{
	if(l==r)return;
	int mid=(l+r)>>1;
	CDQ(l,mid),CDQ(mid+1,r);
	int i=l,j=mid+1,o=0;
	while(i<=mid&&j<=r)
	{
		if(q[i]<=q[j])
		{
			if(q[i].type==1)
				update(q[i].y,q[i].w);
			tmp[o++]=q[i++]; 
		}
		else
		{
			if(q[j].type==2)
				ans[q[j].num]+=query(q[j].y)*q[j].w;
			tmp[o++]=q[j++];	
		}
	}
	while(i<=mid)
	{
		if(q[i].type==1)update(q[i].y,q[i].w);
		tmp[o++]=q[i++];
	}
	while(j<=r)
	{
		if(q[j].type==2)ans[q[j].num]+=query(q[j].y)*q[j].w;
		tmp[o++]=q[j++];
	}
	for(int i=l;i<=mid;i++)
		if(q[i].type==1)update(q[i].y,-q[i].w);
	for(int i=0;i<o;i++)
		q[i+l]=tmp[i];
}
int main()
{
	scanf("%d%d",&s,&w);
	while(true)
	{
		
		int x,y,x1,y1,w;
		int opt;scanf("%d",&opt);
		if(opt==3)break;
		if(opt==1){
			scanf("%d%d%d",&x,&y,&w);
			q[++cnt]=node(1,x,y,0,w);
		}
		if(opt==2){
			scanf("%d%d%d%d",&x,&y,&x1,&y1);
			q[++cnt]=node(2,x-1,y-1,++tot,1);
			q[++cnt]=node(2,x1,y1,tot,1);
			q[++cnt]=node(2,x-1,y1,tot,-1);
			q[++cnt]=node(2,x1,y-1,tot,-1);
			ans[tot]+=s*(x1-x+1)*(y1-y+1);
		}
	}
	CDQ(1,cnt);
	for(int i=1;i<=tot;i++)printf("%d\n",ans[i]);
	return 0;
} 
/*
0 2
1 1 1 1
2 1 1 1 1
3 
*/