BZOJ 2683: 简单题(CDQ 分治)

题面

 

Time Limit: 50 Sec  Memory Limit: 128 MB

Description

你有一个N*N的棋盘，每个格子内有一个整数，初始时的时候全部为0，现在需要维护两种操作：

 

命令	参数限制	内容
1 x y A	1<=x,y<=N，A是正整数	将格子x,y里的数字加上A
2 x1 y1 x2 y2	1<=x1<= x2<=N 1<=y1<= y2<=N	输出x1 y1 x2 y2这个矩形内的数字和
3	无	终止程序

Input

输入文件第一行一个正整数N。

接下来每行一个操作。

 

Output

对于每个2操作，输出一个对应的答案。

 

Sample Input

4
1 2 3 3
2 1 1 3 3
1 2 2 2
2 2 2 3 4
3

Sample Output

3
5

HINT

 

1<=N<=500000,操作数不超过200000个，内存限制20M。

对于100%的数据，操作1中的A不超过2000。

 

解题思路

 

cdq分治，原问题分为三维：时间，横坐标，纵坐标，之后cdq分治解决时间， 排序解决横坐标，树状数组解决纵坐标，时间复杂度O(nlog^2n)

 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
using namespace std;
const int MAXN = 500005;
typedef long long LL;
inline int rd(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)) {f=ch=='-'?0:1;ch=getchar();}
while(isdigit(ch))
{x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return f?x:-x;
}
int n,cnt,Num;
LL f[MAXN],ans[MAXN];
struct Query{
int x,y,type;
int val,id,num;
friend bool operator<(const Query A,const Query B){
if(A.x!=B.x) return A.x<B.x;
if(A.y!=B.y) return A.y<B.y;
return A.type<B.type;
}
}q[MAXN<<2],tmp[MAXN<<2];
void add(int x,int y){
for(;x<=n;x+=x&-x) f[x]+=y;
}
LL sum(int x){
LL ret=0;
for(;x;x-=x&-x) ret+=f[x];
return ret;
}
void Clear(int x){
for(;x<=n;x+=x&-x) f[x]=0;
}
void cdq(int l,int r){
if(l==r) return;
int mid=l+r>>1;cdq(l,mid);cdq(mid+1,r);
int L=l,R=mid+1,o=0;
while(L<=mid && R<=r) {
if(q[L]<q[R]) {
if(q[L].type==1) add(q[L].y,q[L].val);
tmp[++o]=q[L++];
}
else{
if(q[R].type==2) ans[q[R].num]+=q[R].val*sum(q[R].y);
tmp[++o]=q[R++];
}
}
while(L<=mid) tmp[++o]=q[L++];
while(R<=r) {
if(q[R].type==2) ans[q[R].num]+=q[R].val*sum(q[R].y);
tmp[++o]=q[R++];
}
for(register int i=l;i<=mid;i++) if(q[i].type==1) Clear(q[i].y);
for(register int i=1;i<=o;i++) q[i+l-1]=tmp[i];
}
int main(){
n=rd();
int op,x1,x2,y1,y2;
while(1){
op=rd();if(op==3) break;
if(op==1) {
q[++cnt].type=op;q[cnt].x=rd();q[cnt].y=rd();
q[cnt].val=rd();q[cnt].id=cnt;
}
else{
x1=rd(),y1=rd(),x2=rd(),y2=rd();
q[++cnt].type=op;q[cnt].x=x1-1;q[cnt].y=y1-1;
q[cnt].val=1;q[cnt].id=cnt;q[cnt].num=++Num;
q[++cnt].type=op;q[cnt].x=x1-1;q[cnt].y=y2;
q[cnt].val=-1;q[cnt].id=cnt;q[cnt].num=Num;
q[++cnt].type=op;q[cnt].x=x2;q[cnt].y=y1-1;
q[cnt].val=-1;q[cnt].id=cnt;q[cnt].num=Num;
q[++cnt].type=op;q[cnt].x=x2;q[cnt].y=y2;
q[cnt].val=1;q[cnt].id=cnt;q[cnt].num=Num;
}
}
//
cout<<cnt<<endl;
//
for(int i=1;i<=cnt;i++)
//
cout<<q[i].type<<" "<<q[i].x<<" "<<q[i].y<<" "<<q[i].val<<" "<<q[i].id<<" "<<q[i].num<<endl;
cdq(1,cnt);
for(int i=1;i<=Num;i++) printf("%lldn",ans[i]);
return 0;
}