题意：一个n*n的01矩阵，和二种动态操作，一对子矩阵(x1,y1,x2,y2)的所有元素异或，查询某一点(x,y)的元素值。
二维线段树
View Code
1 #include<iostream>
2 using namespace std;
3 int res;
4 struct sub_node
5 {
6 short c,d;
7 bool cnt;
8 };
9 struct node
10 {
11 short a,b;
12 sub_node sub_tree[1100*2];
13 };
14 node tree[1100*2];
15 void sub_maketree(sub_node sub_tree[],int c,int d,int k)
16 {
17 sub_tree[k].c = c;
18 sub_tree[k].d = d;
19 sub_tree[k].cnt = 0;
20 if(c==d) return ;
21 int mid = (c+d)>>1;
22 sub_maketree(sub_tree,c,mid,k<<1);
23 sub_maketree(sub_tree,mid+1,d,k<<1|1);
24 }
25 void maketree(int a,int b,int c,int d,int k) //a,b外层 c,d 内层
26 {
27 tree[k].a = a;
28 tree[k].b = b;
29 sub_maketree(tree[k].sub_tree,c,d,1);
30 if(a==b) return ;
31 int mid = (a+b)>>1;
32 maketree(a,mid,c,d,k<<1);
33 maketree(mid+1,b,c,d,k<<1|1);
34 }
35 void sub_update(sub_node sub_tree[],int c,int d,int k) //O(logN)
36 {
37 if(c<=sub_tree[k].c && sub_tree[k].d <= d)
38 {
39 sub_tree[k].cnt ^= 1; //更新次数
40 return ;
41 }
42 if(c <= sub_tree[k<<1].d)
43 sub_update(sub_tree,c,d,k<<1);
44 if(d >sub_tree[k<<1].d)
45 sub_update(sub_tree,c,d,k<<1|1);
46
47 }
48 void update(int a,int b,int c,int d,int k) //外层:O(logN) * 内层:O(logN)
49 {
50 if(a<=tree[k].a && tree[k].b <= b)
51 {
52 sub_update(tree[k].sub_tree,c,d,1);
53 return ;
54 }
55 if(a<=tree[k<<1].b)
56 update(a,b,c,d,k<<1);
57 if(b > tree[k<<1].b)
58 update(a,b,c,d,k<<1|1);
59
60 }
61 //统计内层y所在的线段被更新的次数O(logN)
62 void Query_sub(sub_node sub_tree[],int y,int k)
63 {
64 res ^= sub_tree[k].cnt;
65 if(sub_tree[k].c == sub_tree[k].d)
66 return ;
67 if(y <= sub_tree[k<<1].d)
68 Query_sub(sub_tree,y,k<<1);
69 else
70 Query_sub(sub_tree,y,k<<1|1);
71 }
72 /*遍历所有包含该点的矩形,统计所有矩形上,
73 点坐标(x,y)被更新的总次数O(logN)*O(logN)*/
74 void Query(int x,int y,int k)
75 {
76 Query_sub(tree[k].sub_tree,y,1);
77 if(tree[k].a == tree[k].b )
78 return ;
79 if(x <= tree[k<<1].b)
80 Query(x,y,k<<1);
81 else
82 Query(x,y,k<<1|1);
83 }
84 int main()
85 {
86 int T,N,M;
87 scanf("%d",&T);
88 char s[3];
89 int x,y,ans;
90 int x1,y1,x2,y2;
91 while(T--)
92 {
93 scanf("%d%d",&N,&M);
94 maketree(1,N,1,N,1);
95 while(M--)
96 {
97 scanf("%s",s);
98 if(s[0] == 'C')
99 {
100 scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
101 update(x1,x2,y1,y2,1);
102 }
103 else
104 {
105 scanf("%d%d",&x,&y);
106 res = 0;
107 Query(x,y,1);
108 printf("%d\n",res);
109 }
110 }
111 printf("\n");
112 }
113 return 0;
114 }