矩阵Matrix（POJ2155）

给一个N*N的矩阵A，此中元素是0或1。A[j]表示在第i行第j列的数。最初时，A[j]=0(1<=i,j<=N)。我们以以下方式来改变矩阵，给定一个矩形的左上角为(x1,y1)和右下角为(x2,y2)，我们对这个矩形范围内的所有元素举行“非”操作（如果它是一个'0'，那么变化为'1'，否则它变为'0'）。
请你编写一个步伐完成以下两种操作：
比较简朴
用二维树状数组，每次区间增加1，然后单点查询每一个点对2取模的值。
好做完了。

1. #include <bits/stdc++.h>
2. using namespace std;
3. const long long N = 1050;
4. long long n,m;
5. class owl{
6. public:
7.         long long tr[N][N];
8.         long long lowbit(long long x){
9.                 return x & -x;
10.         }
11.         void add(long long x,long long y,long long d){
12.                 for (long long i = x; i <= n; i += lowbit(i)){
13.                         for (long long j = y; j <= n; j += lowbit(j)){
14.                                 tr[i][j] += d;
15.                         }
16.                 }
17.         }
18.         long long sum(long long x,long long y){
19.                 long long res = 0;
20.                 for (long long i = x; i ; i -= lowbit(i)){
21.                         for (long long j = y; j; j -= lowbit(j)){
22.                                 res += tr[i][j];
23.                         }
24.                 }
25.                 return res;
26.         }
27. }A,B,C,D;
28. void owladd(long long a,long long b,long long c){
29.         A.add(a,b,c);
30.         B.add(a,b,c * a);
31.         C.add(a,b,c * b);
32.         D.add(a,b,a * b * c);
33. }
34. long long owlsum(long long a,long long b){
35.         return A.sum(a,b) * (a * b + a + b + 1) - B.sum(a,b) * (b + 1) - C.sum(a,b) * (a + 1) + D.sum(a,b);
36. }
37. int main(){
38.         int T;
39.         cin >> T;
40.         while (T -- ){
41.                 cin >> n >> m;
42.                 memset(A.tr,0,sizeof A.tr);
43.                                 memset(B.tr,0,sizeof B.tr);
44.                                 memset(C.tr,0,sizeof C.tr);
45.                                 memset(D.tr,0,sizeof D.tr);
46.                 while (m -- ){
47.                         char op;
48.                         cin >> op;
49.                         if (op == 'C'){
50.                                 long long a,b,c,d,z = 1;
51.                                 cin >> a >> b >> c >> d;
52.                                 owladd(a,b,z);
53.                                 owladd(a,d + 1,-z);
54.                                 owladd(c + 1,b,-z);
55.                                 owladd(c + 1,d + 1,z);
56.                         }
57.                         else if (op == 'Q'){
58.                                 long long a,b,c,d;
59.                                 cin >> a >> b;
60.                                 c = a,d = b;
61.                                 cout << (owlsum(c,d) - owlsum(a - 1,d) - owlsum(c,b - 1) + owlsum(a - 1,b - 1)) % 2 << endl;
62.                         }
63.                 }
64.                 cout << endl;
65.         }
66.         return 0;
67. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。