4066: 简单题
Time Limit: 50 Sec Memory Limit: 20 MBSubmit: 234 Solved: 82
[ Submit][ Status][ Discuss]
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。
接下来每行一个操作。每条命令除第一个数字之外,
均要异或上一次输出的答案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
1 2 3 3
2 1 1 3 3
1 1 1 1
2 1 1 0 7
3
Sample Output
3
5
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; } } }