This has solution for each query (and 1 and 2) has time complexity O(log n). In array f (of length n + 1)we will 
store each query T (i , j) - we set f[i]++ and f[j + 1]--. For each card k between i and j (include i and j) 
sum f[1] + f[2] + ... + f[k] will be increased for 1, for all others will be same as before 
(look at the image 2.0 for clarification), so our solution will be described sum 
(which is same as cumulative frequency) module 2.













看了這之后，是不是發(fā)現(xiàn)原來(lái)還可以這樣啊，呵呵，這就是思維轉(zhuǎn)換了，如果你已經(jīng)知道這中思路了，那么這篇文章基本不用看了，因?yàn)槟阋呀?jīng)會(huì)

好了，接下來(lái)我們說說POJ這題吧，你是不是發(fā)現(xiàn)這題和上面那個(gè)英文描述的題很像呢，只不過這個(gè)是二維的，恩，確實(shí)，其實(shí)上面那個(gè)就是

POJ_2155的一維版本，好了這樣說，你應(yīng)該懂了吧。下面看看代碼吧(建議先自己想哦)，再提供篇集訓(xùn)論文吧

CODE
 1/**//*
 2  ID:Klion
 3  PROG:POJ_2155
 4  LANG:C++
 5 */
 6#include <iostream>
 7using namespace std;
 8int n;
 9int num[1002][1002];
10void update(int x,int y)
11{//這里確實(shí)很帥啊
12       int y1;
13       while(x <= n)
14         {
15            y1 = y;
16            while(y1 <= n)
17              {
18                 num[x][y1] ^= 1;
19                 y1 += (y1 & -y1);
20              }
21            x += (x & -x);  
22         }
23}
24void work(int x1,int y1,int x2,int y2)
25{//主要是這里，好好想清楚
26     update(x1,y1);
27     update(x2+1,y1);
28     update(x1,y2+1);
29     update(x2+1,y2+1);
30}
31int read(int x,int y)
32{
33      int ret=0;
34      int y1;
35      while(x > 0)
36         {
37             y1 = y;
38             while(y1 > 0)
39               {
40                   ret = ((ret + num[x][y1]) & 1);
41                   y1 -= (y1 & -y1);
42               }
43             x -= (x & -x);
44         }
45      ret &= 1;
46      return ret;
47}
48int main(void)
49{
50      freopen("POJ_2155.in","r",stdin);
51      freopen("POJ_2155.out","w",stdout);
52      int t;
53      int x1,y1,x2,y2;
54      int x,y;
55      int l;
56      char str[2];
57      scanf("%d",&t);
58      while(t--)
59         {
60              memset(num,0,sizeof(num));
61              scanf("%d%d%*c",&n,&l);
62              for(int i = 0;i < l;i++)
63                {
64                     scanf("%s",str);
65                     if('Q' == str[0])
66                          {
67                              scanf("%d%d%*c",&x,&y);
68                              printf("%d\n",read(x,y));
69                          }
70                     else
71                          {
72                              scanf("%d%d%d%d%*c",&x1,&y1,&x2,&y2);
73                              work(x1,y1,x2,y2);
74                          }
75                }
76             printf("\n");
77         }
78    return 0;
79}
80