bzoj 4066: 简单题 kd-tree

4066: 简单题

Time Limit: 50 Sec  Memory Limit: 20 MB Submit: 234  Solved: 82 [ 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。 接下来每行一个操作。每条命令除第一个数字之外， 均要异或上一次输出的答案last_ans，初始时last_ans=0。

Output

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

Sample Input

4 1 2 3 3 2 1 1 3 3 1 1 1 1 2 1 1 0 7 3

Sample Output

3 5

HINT

数据规模和约定

 

1<=N<=500000,操作数不超过200000个，内存限制20M，保证答案在int范围内并且解码之后数据仍合法。

 

样例解释见OJ2683   kd-tree （不需要套替罪羊）不用解释了吧。。。。 #include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; #define MAXN 300100 #define MAXT MAXN #define INF 0x3f3f3f3f struct kdt_node { int lc,rc; int xmn,xmx; int ymn,ymx; int sum; int x,y; }kdt[MAXT]; int topt=0; inline void update(int now) { kdt[now].xmn=min(kdt[now].x,min(kdt[kdt[now].lc].xmn,kdt[kdt[now].rc].xmn)); kdt[now].xmx=max(kdt[now].x,max(kdt[kdt[now].lc].xmx,kdt[kdt[now].rc].xmx)); kdt[now].ymn=min(kdt[now].y,min(kdt[kdt[now].lc].ymn,kdt[kdt[now].rc].ymn)); kdt[now].ymx=max(kdt[now].y,max(kdt[kdt[now].lc].ymx,kdt[kdt[now].rc].ymx)); } int x,y,v; void Add_kdt(int &now,int d=0) { if (!now) { now=++topt; kdt[now].x=x; kdt[now].y=y; update(now); } kdt[now].sum+=v; if (kdt[now].x==x && kdt[now].y==y)return ; if (!d) { if (x<=kdt[now].x) { Add_kdt(kdt[now].lc,1-d); }else { Add_kdt(kdt[now].rc,1-d); } }else { if (y<=kdt[now].y) { Add_kdt(kdt[now].lc,1-d); }else { Add_kdt(kdt[now].rc,1-d); } } update(now); } int x1,x2,y1,y2; int Query_kdt(int now,int d) { if (!now)return 0; if (kdt[now].xmn>=x1 && kdt[now].xmx<=x2 && kdt[now].ymn>=y1 && kdt[now].ymx<=y2) return kdt[now].sum; int ret=0; if (kdt[now].x<=x2 && kdt[now].x>=x1 && kdt[now].y<=y2 && kdt[now].y>=y1)ret+=kdt[now].sum-kdt[kdt[now].lc].sum-kdt[kdt[now].rc].sum; if (!d) { if (x1<=kdt[now].x) ret+=Query_kdt(kdt[now].lc,1-d); if (x2>kdt[now].x) ret+=Query_kdt(kdt[now].rc,1-d); }else { if (y1<=kdt[now].y) ret+=Query_kdt(kdt[now].lc,1-d); if (y2>kdt[now].y) ret+=Query_kdt(kdt[now].rc,1-d); } return ret; } int main() { // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); int n,m; scanf("%d",&n); int root=0; int opt=0; int lastans=0; kdt[0].xmn=kdt[0].ymn=INF; kdt[0].xmx=kdt[0].ymx=-INF; while (true) { scanf("%d",&opt); if (opt==1) { scanf("%d%d%d",&x,&y,&v); x^=lastans;y^=lastans;v^=lastans; Add_kdt(root,0); }else if (opt==2) { scanf("%d%d%d%d",&x1,&y1,&x2,&y2); x1^=lastans;x2^=lastans;y1^=lastans;y2^=lastans; printf("%d\n",lastans=Query_kdt(root,0)); }else { break; } } }

 

 

转载于:https://www.cnblogs.com/mhy12345/p/4511037.html