bzoj 2683: 简单题 （KD-tree）

2683: 简单题

Time Limit: 50 Sec  Memory Limit: 128 MB Submit: 1098  Solved: 436 [ Submit][ Status][ Discuss]

Description

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

 

命令

参数限制

内容

1 x y A

1<=x,y<=N，A是正整数

将格子x,y里的数字加上A

2 x₁ y₁ x₂ y₂

1<=x₁<= x₂<=N

1<=y₁<= y₂<=N

输出x₁ y₁ x₂ y₂这个矩形内的数字和

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。

Source

[ Submit][ Status][ Discuss]

题解：KD-tree

与bzoj 4066做法相同，只不过不用强制在线，那么应该可以用cdq之类的做。

#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #define N 200003 using namespace std; int n,m,root,cmpd,x,y,x0,y0,a,ans; struct data{ int d[2],mx[2],mn[2],sum,l,r,val; }tr[N]; int cmp(data a,data b) { return a.d[cmpd]<b.d[cmpd]||a.d[cmpd]==b.d[cmpd]&&a.d[cmpd^1]<b.d[cmpd^1]; } void update(int now) { int l=tr[now].l; int r=tr[now].r; for (int i=0;i<=1;i++) { if (l) tr[now].mx[i]=max(tr[now].mx[i],tr[l].mx[i]), tr[now].mn[i]=min(tr[now].mn[i],tr[l].mn[i]); if (r) tr[now].mx[i]=max(tr[now].mx[i],tr[r].mx[i]), tr[now].mn[i]=min(tr[now].mn[i],tr[r].mn[i]); } if (l) tr[now].sum+=tr[l].sum; if (r) tr[now].sum+=tr[r].sum; } int rebuild(int l,int r,int d) { cmpd=d; int mid=(l+r)/2; nth_element(tr+l,tr+mid,tr+r+1,cmp); for (int i=0;i<=1;i++) tr[mid].mx[i]=tr[mid].mn[i]=tr[mid].d[i]; tr[mid].sum=tr[mid].val; tr[mid].l=tr[mid].r=0; if (l<mid) tr[mid].l=rebuild(l,mid-1,d^1); if (r>mid) tr[mid].r=rebuild(mid+1,r,d^1); update(mid); return mid; } void insert(int now) { if (!root) { root=now; return; } int x=root; int d=0; while (true) { for (int i=0;i<=1;i++) tr[x].mx[i]=max(tr[x].mx[i],tr[now].mx[i]), tr[x].mn[i]=min(tr[x].mn[i],tr[now].mn[i]); tr[x].sum+=tr[now].sum; //cout<<tr[x].d[0]<<" "<<tr[x].d[1]<<" "<<tr[x].sum<<endl; if (tr[now].d[d]>=tr[x].d[d]) { if (!tr[x].r) { tr[x].r=now; return; }else x=tr[x].r; } else { if (!tr[x].l) { tr[x].l=now; return; } else x=tr[x].l; } d^=1; } } int pd(int now) { int nowx=tr[now].d[0]; int nowy=tr[now].d[1]; if (nowx>=x&&nowx<=x0&&nowy>=y&&nowy<=y0) return 1; else return 0; } int check(int now) { if (tr[now].mx[0]<=x0&&tr[now].mn[0]>=x&&tr[now].mx[1]<=y0&&tr[now].mn[1]>=y) return 1; if (tr[now].mx[0]<x||tr[now].mn[0]>x0||tr[now].mx[1]<y||tr[now].mn[1]>y0) return -1; return 0; } void query(int now) { if (pd(now)) ans+=tr[now].val; if (tr[now].l) { int t=check(tr[now].l); if (t==1) ans+=tr[tr[now].l].sum; else if (t==0) query(tr[now].l); } if (tr[now].r) { int t=check(tr[now].r); if (t==1) ans+=tr[tr[now].r].sum; else if (t==0) query(tr[now].r); } } int main() { scanf("%d",&m); while (true) { int opt; scanf("%d",&opt); if (opt==3) break; if (opt==1) { scanf("%d%d%d",&x,&y,&a); ++n; tr[n].d[0]=tr[n].mx[0]=tr[n].mn[0]=x; tr[n].d[1]=tr[n].mx[1]=tr[n].mn[1]=y; tr[n].val=tr[n].sum=a; insert(n); if (n000==0) root=rebuild(1,n,0); } if (opt==2) { scanf("%d%d%d%d",&x,&y,&x0,&y0); ans=0; query(root); printf("%d\n",ans); } } }