Codeforces Round #149 (Div. 2) E. XOR on Segment (线段树成段更新+二进制)

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cmath>
  4 #include <cstring>
  5 using namespace std;
  6 const int MAXN = 1e5 + 5;
  7 typedef __int64 LL;
  8 struct segtree {
  9     int l , r , lazy , bit[21];
 10 }T[MAXN << 2];
 11 LL Res;
 12 
 13 void init(int p , int l , int r) {
 14     int mid = (l + r) >> 1;
 15     T[p].r = r , T[p].l = l , T[p].lazy = 0;
 16     if(l == r) {
 17         int num;
 18         scanf("%d" , &num);
 19         for(int i = 0 ; i < 21 ; i++) {
 20             T[p].bit[i] = ((num & 1) ? 1:0 );
 21             num >>= 1;
 22         }
 23         return ;
 24     }
 25     init(p << 1 , l , mid);
 26     init((p << 1)|1 , mid + 1 , r);
 27     for(int i = 0 ; i < 21 ; i++) {
 28         T[p].bit[i] = T[p << 1].bit[i] + T[(p << 1)|1].bit[i];
 29     }
 30 }
 31 
 32 void updata(int p , int l , int r , int x) {
 33     int mid = (T[p].l + T[p].r) >> 1;
 34     if(l == T[p].l && T[p].r == r) {
 35         T[p].lazy ^= x;
 36         for(int i = 0 ; i < 21 ; i++) {
 37             if(x % 2)
 38                 T[p].bit[i] = (T[p].r - T[p].l + 1) - T[p].bit[i];
 39             x >>= 1;
 40         }
 41         return ;
 42     }
 43     if(T[p].lazy) {
 44         T[p << 1].lazy ^= T[p].lazy;
 45         T[(p << 1)|1].lazy ^= T[p].lazy;
 46         for(int i = 0 ; i < 21 ; i++) {
 47             if(T[p].lazy & 1) {
 48                 T[p << 1].bit[i] = (T[p << 1].r - T[p << 1].l + 1) - T[p << 1].bit[i];
 49                 T[(p << 1)|1].bit[i] = (T[(p << 1)|1].r - T[(p << 1)|1].l + 1) - T[(p << 1)|1].bit[i];
 50             }
 51             T[p].lazy >>= 1;
 52         }
 53     }
 54     if(r <= mid) { 
 55         updata(p << 1 , l , r , x);
 56     }
 57     else if(l > mid) {
 58         updata((p << 1)|1 , l , r , x);
 59     }
 60     else {
 61         updata(p << 1 , l , mid , x);
 62         updata((p << 1)|1 , mid + 1 , r , x);
 63     }
 64     for(int i = 0 ; i < 21 ; i++) {
 65         T[p].bit[i] = T[p << 1].bit[i] + T[(p << 1)|1].bit[i];
 66     }
 67 }
 68 
 69 void query(int p , int l , int r) {
 70     int mid = (T[p].l + T[p].r) >> 1;
 71     if(l == T[p].l && T[p].r == r) {
 72         for(int i = 0 ; i < 21 ; i++) {
 73             if(T[p].bit[i])
 74                 Res += (LL)T[p].bit[i] * (LL)(1 << i);
 75         }
 76         return ;
 77     }
 78     if(T[p].lazy) {
 79         T[p << 1].lazy ^= T[p].lazy;
 80         T[(p << 1)|1].lazy ^= T[p].lazy;
 81         for(int i = 0 ; i < 21 ; i++) {
 82             if(T[p].lazy & 1) {
 83                 T[p << 1].bit[i] = (T[p << 1].r - T[p << 1].l + 1) - T[p << 1].bit[i];
 84                 T[(p << 1)|1].bit[i] = (T[(p << 1)|1].r - T[(p << 1)|1].l + 1) - T[(p << 1)|1].bit[i];
 85             }
 86             T[p].lazy >>= 1;
 87         }
 88     }
 89     if(r <= mid) {
 90         query(p << 1 , l , r);
 91     }
 92     else if(l > mid) {
 93         query((p << 1)|1 , l , r);
 94     }
 95     else {
 96         query(p << 1 , l , mid);
 97         query((p << 1)|1 , mid + 1 , r);
 98     }
 99     for(int i = 0 ; i < 21 ; i++) {
100         T[p].bit[i] = T[p << 1].bit[i] + T[(p << 1)|1].bit[i];
101     }
102 }
103 
104 int main()
105 {
106     int n , m , c , x , l , r;
107     scanf("%d" , &n);
108     init(1 , 1 , n);
109     scanf("%d" , &m);
110     while(m--) {
111         scanf("%d" , &c);
112         if(c == 1) {
113             scanf("%d %d" , &l , &r);
114             Res = 0;
115             query(1 , l , r);
116             printf("%I64d\n" , Res);
117         }
118         else {
119             scanf("%d %d %d" , &l , &r , &x);
120             updata(1 , l , r , x);
121         }
122     }
123 }