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范围内并且解码之后数据仍合法。
因为把1写成2挂了半天没找到错误ummm……
其他操作都是K-D Tree常规操作,唯一需要改改的就是查询的时候,
若当前KDT节点子树的矩形范围在查询范围外面就return
若当前KDT节点子树的矩形范围全在查询范围里面就统计子树答案return
记得判断一下查询的时候经过的叶子节点是否符合条件,符合则统计一下
其他操作都是K-D Tree常规操作,唯一需要改改的就是查询的时候,
若当前KDT节点子树的矩形范围在查询范围外面就return
若当前KDT节点子树的矩形范围全在查询范围里面就统计子树答案return
记得判断一下查询的时候经过的叶子节点是否符合条件,符合则统计一下
1 #include<iostream> 2 #include<cstring> 3 #include<cstdlib> 4 #include<cstdio> 5 #include<cmath> 6 #include<algorithm> 7 #define N (200000+1000) 8 using namespace std; 9 10 int n,opt,x,y,X[2],Y[2],k,D,Root,ans,lastans; 11 int stack[N],top,cnt; 12 double alpha=0.75; 13 14 int NewNode() 15 { 16 if (top) return stack[top--]; 17 return ++cnt; 18 } 19 20 struct Node 21 { 22 int d[2],Max[2],Min[2],lson,rson,sum,val,size; 23 bool operator < (const Node &a) const {return d[D]<a.d[D];} 24 Node (int x=0,int y=0,int z=0) 25 { 26 d[0]=x; d[1]=y; lson=rson=0; sum=val=z; size=0; 27 Max[0]=Min[0]=d[0]; Max[1]=Min[1]=d[1]; 28 } 29 }p[N]; 30 31 struct KDT 32 { 33 Node Tree[N]; 34 35 void Update(int now) 36 { 37 int ls=Tree[now].lson, rs=Tree[now].rson; 38 for (int i=0; i<=1; ++i) 39 { 40 Tree[now].Max[i]=Tree[now].Min[i]=Tree[now].d[i]; 41 if (ls) 42 { 43 Tree[now].Max[i]=max(Tree[now].Max[i],Tree[ls].Max[i]); 44 Tree[now].Min[i]=min(Tree[now].Min[i],Tree[ls].Min[i]); 45 } 46 if (rs) 47 { 48 Tree[now].Max[i]=max(Tree[now].Max[i],Tree[rs].Max[i]); 49 Tree[now].Min[i]=min(Tree[now].Min[i],Tree[rs].Min[i]); 50 } 51 } 52 Tree[now].sum=Tree[ls].sum+Tree[rs].sum+Tree[now].val; 53 Tree[now].size=Tree[ls].size+Tree[rs].size+1; 54 } 55 int Build(int opt,int l,int r) 56 { 57 if (l>r) return 0; 58 int mid=(l+r)>>1, now=NewNode(); 59 D=opt; nth_element(p+l,p+mid,p+r+1); 60 Tree[now]=p[mid]; 61 Tree[now].lson=Build(opt^1,l,mid-1); 62 Tree[now].rson=Build(opt^1,mid+1,r); 63 Update(now); return now; 64 } 65 void Dfs(int now,int num) 66 { 67 int ls=Tree[now].lson, rs=Tree[now].rson; 68 if (ls) Dfs(ls,num); 69 p[num+Tree[ls].size]=Tree[now]; stack[++top]=now; 70 if (rs) Dfs(rs,num+Tree[ls].size+1); 71 } 72 void Check(int &now,int opt) 73 { 74 int ls=Tree[now].lson, rs=Tree[now].rson; 75 if (Tree[ls].size>Tree[now].size*alpha || Tree[rs].size>Tree[now].size*alpha) 76 Dfs(now,1), now=Build(opt,1,Tree[now].size); 77 } 78 void Insert(int &now,int x,int opt) 79 { 80 if (now==0){Root=x; return;} 81 if (Tree[x].d[opt]<=Tree[now].d[opt]) 82 { 83 if (Tree[now].lson) Insert(Tree[now].lson,x,opt^1); 84 else Tree[now].lson=x; 85 } 86 else 87 { 88 if (Tree[now].rson) Insert(Tree[now].rson,x,opt^1); 89 else Tree[now].rson=x; 90 } 91 Update(now); Check(now,opt); 92 } 93 void Query(int now) 94 { 95 if (Tree[now].Max[0]<X[0] || Tree[now].Max[1]<Y[0] || Tree[now].Min[0]>X[1] || Tree[now].Min[1]>Y[1]) return; 96 if (Tree[now].Max[0]<=X[1] && Tree[now].Min[0]>=X[0] && Tree[now].Max[1]<=Y[1] && Tree[now].Min[1]>=Y[0]) 97 { 98 ans+=Tree[now].sum; 99 return; 100 } 101 if (Tree[now].d[0]<=X[1] && Tree[now].d[0]>=X[0] && Tree[now].d[1]<=Y[1] && Tree[now].d[1]>=Y[0]) ans+=Tree[now].val; 102 if (Tree[now].lson) Query(Tree[now].lson); 103 if (Tree[now].rson) Query(Tree[now].rson); 104 } 105 }KDT; 106 107 int main() 108 { 109 scanf("%d",&n); 110 while (1) 111 { 112 scanf("%d",&opt); 113 if (opt==1) 114 { 115 scanf("%d%d%d",&x,&y,&k); 116 x^=lastans; y^=lastans; k^=lastans; 117 int t=NewNode(); 118 KDT.Tree[t]=Node(x,y,k); 119 KDT.Tree[t].size=1; 120 KDT.Insert(Root,t,0); 121 } 122 if (opt==2) 123 { 124 scanf("%d%d%d%d",&X[0],&Y[0],&X[1],&Y[1]); 125 X[0]^=lastans; Y[0]^=lastans; 126 X[1]^=lastans; Y[1]^=lastans; 127 ans=0; 128 KDT.Query(Root); 129 printf("%d\n",ans); 130 lastans=ans; 131 } 132 if (opt==3) break; 133 } 134 }