Codeforces 242E：XOR on Segment（位上的线段树）***-白红宇

Codeforces 242E：XOR on Segment（位上的线段树）***

阅读量：4615 次

发布时间：2019-06-09

本文共 2630 字，大约阅读时间需要 8 分钟。

题意：给出初始n个数，还有m个操作，操作一种是区间求和，一种是区间xor x。

思路：昨天比赛出的一道类似题目，对于一个数，把它变成二进制，那么做xor操作的时候，其实如果那一位xor 1，那么就是取反，否则不变。于是，可以对每一个二进制位开一棵线段树，由于数字最大有1e6，所以只需要开log(1e6) = 20棵线段树。对每一棵线段树统计区间内1的个数，那一位对答案的贡献就是那一位的权值*区间1的个数。在作xor操作的时候，如果是xor的数1，那么就是区间内所有的1变成0，0变成1，这一段的和就变成（长度 - 原本的值），否则不变。

pushdown操作对右子树操作少了一个|1，导致调试好久，一定要细心！

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 #include 
           
             8 #include 
            
              9 #include 
             10 #include 
              
               11 #include 
               
                12 using namespace std;13 typedef long long LL;14 #define N 10001015 #define INF 0x3f3f3f3f16 #define lson rt<<1, l, m17 #define rson rt<<1|1, m+1, r18 int tree[21][N<<2], lazy[21][N<<2], bit[21];19 LL weight[21];20 21 void pushup(int id, int rt) { tree[id][rt] = tree[id][rt<<1] + tree[id][rt<<1|1]; }22 23 void pushdown(int id, int rt, int len, int l, int r) {24 if(lazy[id][rt]) {25 tree[id][rt<<1] = (len - len / 2) - tree[id][rt<<1];26 tree[id][rt<<1|1] = (len / 2) - tree[id][rt<<1|1];27 lazy[id][rt<<1] ^= 1; lazy[id][rt<<1|1] ^= 1;28 lazy[id][rt] = 0;29 }30 }31 32 void update(int id, int rt, int l, int r, int L, int R, int w) {33 if(L <= l && r <= R) {34 if(w) tree[id][rt] = (r - l + 1 - tree[id][rt]);35 lazy[id][rt] ^= w;36 return ;37 }38 pushdown(id, rt, r - l + 1, l, r);39 int m = (l + r) >> 1;40 if(L <= m) update(id, lson, L, R, w);41 if(m < R) update(id, rson, L, R, w);42 pushup(id, rt);43 }44 45 int query(int id, int rt, int l, int r, int L, int R) {46 if(L <= l && r <= R) return tree[id][rt];47 pushdown(id, rt, r - l + 1, l, r);48 int m = (l + r) >> 1;49 int ans = 0;50 if(L <= m) ans += query(id, lson, L, R);51 if(m < R) ans += query(id, rson, L, R);52 return ans;53 }54 55 int main()56 {57 int n, num, q, maxn = 0;58 scanf("%d", &n);59 for(int i = 1; i <= 20; i++) weight[i] = 1LL << (i - 1);60 for(int i = 1; i <= n; i++) {61 scanf("%d", &num);62 int tmp = num, cnt = 0;63 while(tmp) {64 bit[++cnt] = tmp & 1;65 tmp >>= 1;66 }67 if(cnt > maxn) maxn = cnt;68 for(int j = cnt; j >= 1; j--) update(j, 1, 1, n, i, i, bit[j]);69 }70 scanf("%d", &q);71 while(q--) {72 int type, l, r, w;73 scanf("%d%d%d", &type, &l, &r);74 if(type == 1) {75 LL ans = 0;76 for(int i = 1; i <= maxn; i++) {77 int num = query(i, 1, 1, n, l, r);78 ans += weight[i] * num;79 }80 printf("%I64d\n", ans);81 } else {82 scanf("%d", &w);83 int cnt = 0;84 while(w) {85 bit[++cnt] = w & 1;86 w >>= 1;87 }88 if(cnt > maxn) maxn = cnt;89 for(int j = cnt; j >= 1; j--) update(j, 1, 1, n, l, r, bit[j]);90 }91 }92 return 0;93 }

转载于:https://www.cnblogs.com/fightfordream/p/6289609.html

你可能感兴趣的文章