problem Iahub and Xors
题目大意
一个n*n的矩阵，要求支持两种操作。
操作1：将一个子矩阵的所有值异或某个数。
操作2：询问某个子矩阵的所以值的异或和。
解题分析
由于异或的特殊性，可以用二维树状数组来维护。
因为同一个值只有异或奇数次才有效，因此若单点修改某个点，那么其影响的点为与其行和列奇偶性相同的点，故可以开4个二维树状数组来维护。
如果是区间修改x1,y1,x2,y2,则只需单点修改(x1,y1)、(x1,y2+1)、(x2+1,y2)、(x2+1,y2+1)
如果是区间询问x1,y1,x2,y2，则答案为(x2,y2)^(x1-1,y1-1)^(x1-1,y2)^(x2,y1-1)
参考程序
二维树状数组
1 #include <map> 2 #include <set> 3 #include <stack> 4 #include <queue> 5 #include <cmath> 6 #include <ctime> 7 #include <string> 8 #include <vector> 9 #include <cstdio> 10 #include <cstdlib> 11 #include <cstring> 12 #include <cassert> 13 #include <iostream> 14 #include <algorithm> 15 #pragma comment(linker,"/STACK:102400000,102400000") 16 using namespace std; 17 18 #define N 1008 19 #define M 50008 20 #define LL long long 21 #define lson l,m,rt<<1 22 #define rson m+1,r,rt<<1|1 23 #define clr(x,v) memset(x,v,sizeof(x)); 24 #define bitcnt(x) __builtin_popcount(x) 25 #define rep(x,y,z) for (int x=y;x<=z;x++) 26 #define repd(x,y,z) for (int x=y;x>=z;x--) 27 const int mo = 1000000007; 28 const int inf = 0x3f3f3f3f; 29 const int INF = 2000000000; 30 /**************************************************************************/ 31 32 struct Binary_Indexd_Tree{ 33 LL a[2][2][N][N]; 34 int n; 35 void init(int x) 36 { 37 n=x; 38 clr(a,0); 39 } 40 void update(int x,int y,LL val) 41 { 42 for (int i=x;i<=n+5;i+=i & (-i)) 43 for (int j=y;j<=n+5;j+=j & (-j)) 44 a[x & 1][y & 1][i][j]^=val; 45 } 46 LL query(int x,int y) 47 { 48 LL res=0; 49 for (int i=x;i;i-=i & (-i)) 50 for (int j=y;j;j-=j & (-j)) 51 res^=a[x & 1][y & 1][i][j]; 52 return res; 53 } 54 }T; 55 56 int main() 57 { 58 int n,q; 59 scanf("%d",&n); 60 T.init(n); 61 scanf("%d",&q); 62 rep(i,1,q) 63 { 64 int op,x1,y1,x2,y2; 65 LL val; 66 scanf("%d%d%d%d%d",&op,&x1,&y1,&x2,&y2); 67 if (op==2) 68 { 69 scanf("%I64d",&val); 70 T.update(x1,y1,val); 71 T.update(x1,y2+1,val); 72 T.update(x2+1,y1,val); 73 T.update(x2+1,y2+1,val); 74 } 75 else 76 { 77 LL res=T.query(x2,y2); 78 res^=T.query(x1-1,y1-1); 79 res^=T.query(x1-1,y2); 80 res^=T.query(x2,y1-1); 81 printf("%I64d ",res); 82 } 83 } 84 }
四分树 T了= =
1 #include <map> 2 #include <set> 3 #include <stack> 4 #include <queue> 5 #include <cmath> 6 #include <ctime> 7 #include <string> 8 #include <vector> 9 #include <cstdio> 10 #include <cstdlib> 11 #include <cstring> 12 #include <cassert> 13 #include <iostream> 14 #include <algorithm> 15 #pragma comment(linker,"/STACK:102400000,102400000") 16 using namespace std; 17 18 #define N 3008 19 #define M 50008 20 #define LL long long 21 #define son(x) rt*4+x-3 22 #define clr(x,v) memset(x,v,sizeof(x)); 23 #define bitcnt(x) __builtin_popcount(x) 24 #define rep(x,y,z) for (int x=y;x<=z;x++) 25 #define repd(x,y,z) for (int x=y;x>=z;x--) 26 const int mo = 1000000007; 27 const int inf = 0x3f3f3f3f; 28 const int INF = 2000000000; 29 /**************************************************************************/ 30 31 LL tag[N*N],lazy[N*N]; 32 struct interval{ 33 int l,r; 34 interval(int l=0,int r=0):l(l),r(r){} 35 int mid(){ 36 return l+r>>1; 37 } 38 int len(){ 39 return r-l+1; 40 } 41 interval left(){ 42 return interval(l,mid()); 43 } 44 interval right(){ 45 return interval(mid()+1,r); 46 } 47 bool intersect(interval x) 48 { 49 return !(x.r<l || x.l>r); 50 } 51 bool contain(interval x) 52 { 53 return l<=x.l && x.r<=r; 54 } 55 bool pt() 56 { 57 printf("%d %d ",l,r); 58 } 59 }; 60 void pushup(int rt) 61 { 62 tag[rt]=tag[son(1)]^tag[son(2)]^tag[son(3)]^tag[son(4)]; 63 } 64 void pushdown(int rt,interval x,interval y) 65 { 66 if (lazy[rt]) 67 { 68 lazy[son(1)]^=lazy[rt]; 69 lazy[son(2)]^=lazy[rt]; 70 lazy[son(3)]^=lazy[rt]; 71 lazy[son(4)]^=lazy[rt]; 72 if (x.left().len() * y.left().len() & 1) tag[son(1)]^=lazy[rt]; 73 if (x.left().len() * y.right().len() & 1) tag[son(2)]^=lazy[rt]; 74 if (x.right().len() * y.left().len() & 1) tag[son(3)]^=lazy[rt]; 75 if (x.right().len() * y.right().len() & 1) tag[son(4)]^=lazy[rt]; 76 lazy[rt]=0; 77 } 78 } 79 void build(interval x,interval y,int rt) 80 { 81 tag[rt]=0; lazy[rt]=0; 82 if (x.len()<=0 || y.len()<=0) return; 83 if (x.len()==1 && y.len()==1) 84 { 85 return; 86 } 87 build(x.left(),y.left(),son(1)); 88 build(x.left(),y.right(),son(2)); 89 build(x.right(),y.left(),son(3)); 90 build(x.right(),y.right(),son(4)); 91 pushup(rt); 92 } 93 LL query(interval X,interval Y,interval x,interval y,int rt) 94 { 95 if (x.len()<=0 || y.len()<=0) return 0; 96 if (!x.intersect(X) || !y.intersect(Y)) return 0; 97 if (X.contain(x) && Y.contain(y)) 98 { 99 return tag[rt]; 100 } 101 pushdown(rt,x,y); 102 LL res=0; 103 res^=query(X,Y,x.left(),y.left(),son(1)); 104 res^=query(X,Y,x.left(),y.right(),son(2)); 105 res^=query(X,Y,x.right(),y.left(),son(3)); 106 res^=query(X,Y,x.right(),y.right(),son(4)); 107 //x.pt(); y.pt(); printf("%lld ",res); 108 return res; 109 } 110 void update(interval X,interval Y,LL val,interval x,interval y,int rt) 111 { 112 if (x.len()<=0 || y.len()<=0) return; 113 if (!X.intersect(x) || !Y.intersect(y)) return; 114 if (X.contain(x) && Y.contain(y)) 115 { 116 if (x.len()*y.len() & 1) tag[rt]^=val; 117 lazy[rt]^=val; 118 return; 119 } 120 pushdown(rt,x,y); 121 update(X,Y,val,x.left(),y.left(),son(1)); 122 update(X,Y,val,x.left(),y.right(),son(2)); 123 update(X,Y,val,x.right(),y.left(),son(3)); 124 update(X,Y,val,x.right(),y.right(),son(4)); 125 pushup(rt); 126 } 127 int main() 128 { 129 int n,q; 130 scanf("%d%d",&n,&q); 131 build(interval(1,n),interval(1,n),1); 132 while (q--) 133 { 134 int x1,y1,x2,y2,op,val; 135 scanf("%d%d%d%d%d",&op,&x1,&y1,&x2,&y2); 136 if (op==2) 137 { 138 scanf("%d",&val); 139 update(interval(x1,x2),interval(y1,y2),val,interval(1,n),interval(1,n),1); 140 } 141 else 142 { 143 cout << query(interval(x1,x2),interval(y1,y2),interval(1,n),interval(1,n),1)<< endl; 144 } 145 } 146 }