传送门

CDQ分治

cdq分治的练习题，第一次接触这样的离线思路。莫队的离线方法是把区间的询问排序处理。而这个则是把所有询问当成线段来看，把对一个矩阵的询问换成了统计某几个询问对后面几个询问的贡献，非常巧妙的思路。

CDQ分治的基本不说，这个的关键是用CDQ分治来对询问分治。输入数据不变。来维护时间上的单调性。然后对于每一次的区间统计，按$x$的值递增排序。然后对于左区间的每个贡献，统计到右区间。具体的统计方法是用以$y$轴建个树状数组。然后$x$值递增，对于左边的具体贡献及时统计到右区间即可。需要注意的是，直接的矩形询问不好处理。考虑把$(x_1,y_1)$到$(x_2,y_2)$的矩阵拆成$(x_1-1,y_1-1),(x_1-1,y_2),(x_2,y_1-1),(x_2,y_2)$然后容斥原理搞搞就行了。

//BZOJ 2683//by Cydiater//2016.10.12#include <iostream>#include <cstring>#include <string>#include <algorithm>#include <queue>#include <map>#include <ctime>#include <cmath>#include <cstdlib>#include <iomanip>#include <cstdio>using namespace std;#define ll long long#define up(i,j,n)		for(int i=j;i<=n;i++)#define down(i,j,n)		for(int i=j;i>=n;i--)const int MAXN=1e6+5;const int oo=0x3f3f3f3f;inline int read(){	char ch=getchar();int x=0,f=1;	while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)f=-1;ch=getchar();}	while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}	return x*f;}int N,M=0;int c[MAXN];struct Node{	int x,y,f,id;ll ans;}a[MAXN],b[MAXN];namespace solution{	inline bool re_cmp(Node x,Node y){return x.id<y.id;}	inline int lowbit(int i){return((i)&(-i));}	void init(){		N=read();int f;		while((f=read())!=3){			if(f==1){				int x=read(),y=read(),v=read();				a[++M]=(Node){x,y,1,M,v};//add point			}else{				int A=read(),b=read(),c=read(),d=read();				int x=min(A,c),y=min(b,d),X=max(A,c),Y=max(b,d);				a[++M]=(Node){x-1,y-1,0,M,0};a[++M]=(Node){X,y-1,0,M,0};				a[++M]=(Node){x-1,Y,0,M,0};a[++M]=(Node){X,Y,0,M,0};			}		}	}	void insert(int pos,int v){for(int i=pos;i<=N;i+=lowbit(i))c[i]+=v;}	ll get(int pos){		int tmp=0;		for(int i=pos;i>=1;i-=lowbit(i))tmp+=c[i];		return tmp;	}	void slove(int leftt,int rightt){		if(leftt==rightt)return;		int mid=(leftt+rightt)>>1;		slove(leftt,mid);slove(mid+1,rightt);		int point=leftt;		up(i,mid+1,rightt)if(a[i].f==0){			int lim=a[i].x;			while(point<=mid&&a[point].x<=lim){				if(a[point].f!=1){point++;continue;}				insert(a[point].y,a[point].ans);				point++;			}			a[i].ans+=get(a[i].y);		}		int j=leftt,k=mid+1;		up(i,leftt,point-1)if(a[i].f==1)insert(a[i].y,-a[i].ans);		up(i,leftt,rightt)b[i]=((j<=mid&&a[j].x<a[k].x)||k>rightt)?a[j++]:a[k++];		up(i,leftt,rightt)a[i]=b[i];	}	void output(){		sort(a+1,a+M+1,re_cmp);		up(i,1,M)if(a[i].f==0){			ll ans=0;ans=a[i+3].ans-a[i+2].ans-a[i+1].ans+a[i].ans;			i+=3;			printf("%d\n",ans);		}	}}int main(){	//freopen("input.in","r",stdin);	using namespace solution;	init();	slove(1,M);	output();	return 0;}

BZOJ2683: 简单题