codevs 1690 线段树

“反转类问题”需要注意的是pushdown懒标记的时候要用异或（或者++%2）而不是赋值，因为它是和奇偶性有关系的。
  1 #include <iostream>
  2 #include <cstring>
  3 #include <cstdio>
  4 using namespace std;
  5 
  6 const int N = 100001;
  7 
  8 struct Node 
  9 {
 10     int l, r, sum, rev;
 11 } node[N << 2];
 12 
 13 void pushup( int i )
 14 {
 15     node[i].sum = node[i << 1].sum + node[i << 1 | 1].sum;
 16 }
 17 
 18 void build( int i, int l, int r )
 19 {
 20     node[i].l = l, node[i].r = r, node[i].rev = node[i].sum = 0;
 21     if ( l == r ) return ;
 22     int mid = ( l + r ) >> 1;
 23     build( i << 1, l, mid );
 24     build( i << 1 | 1, mid + 1, r );
 25 }
 26 
 27 void pushdown( int i )
 28 {
 29     if ( node[i].rev )
 30     {
 31         int lc = i << 1, rc = lc | 1;
 32         node[lc].rev ^= 1;
 33         node[rc].rev ^= 1;
 34         node[lc].sum = node[lc].r - node[lc].l + 1 - node[lc].sum;
 35         node[rc].sum = node[rc].r - node[rc].l + 1 - node[rc].sum;
 36         node[i].rev = 0;
 37     }
 38 }
 39 
 40 void update( int i, int l, int r )
 41 {
 42     if ( node[i].l == l && node[i].r == r )
 43     {
 44         node[i].sum = node[i].r - node[i].l + 1 - node[i].sum;
 45         node[i].rev ^= 1;
 46         return ;
 47     }
 48     pushdown(i);
 49     int mid = ( node[i].l + node[i].r ) >> 1;
 50     if ( r <= mid )
 51     {
 52         update( i << 1, l, r );
 53     }
 54     else if ( l > mid )
 55     {
 56         update( i << 1 | 1, l, r );
 57     }
 58     else
 59     {
 60         update( i << 1, l, mid );
 61         update( i << 1 | 1, mid + 1, r );
 62     }
 63     pushup(i);    
 64 }
 65 
 66 int query( int i, int l, int r )
 67 {
 68     if ( node[i].l == l && node[i].r == r )
 69     {
 70         return node[i].sum;
 71     }
 72     pushdown(i);
 73     int mid = ( node[i].l + node[i].r ) >> 1;
 74     if ( r <= mid )
 75     {
 76         return query( i << 1, l, r );
 77     }
 78     else if ( l > mid )
 79     {
 80         return query( i << 1 | 1, l, r );
 81     }
 82     else
 83     {
 84         return query( i << 1, l, mid ) + query( i << 1 | 1, mid + 1, r );
 85     }
 86 }
 87 
 88 int main ()
 89 {
 90     int n, m;
 91     while ( scanf("%d%d", &n, &m) != EOF )
 92     {
 93         build( 1, 1, n );
 94         while ( m-- )
 95         {
 96             int op, x, y;
 97             scanf("%d%d%d", &op, &x, &y);
 98             if ( op == 0 )
 99             {
100                 update( 1, x, y );
101             }
102             else
103             {
104                 printf("%d
", query( 1, x, y ));
105             }
106         }
107     }
108     return 0;
109 }