红球进黑洞【线段树区间更新+二进制异或处理】【牛客小白月赛9-C】

题目链接

  给你N个点，M次查询，问的是（一）、区间【l, r】的数的总和；（二）、把区间【l, r】上的所有点去异或（xor）一个数X。

  一开始用了点更新，然后T了，想了一会，最后在比赛结束前终于美滋滋的完成了AC，庆幸，我的想法是这样的，将每个点的值用一个另开的[22]位二进制来存。放心，22位是绝对够的，然后向上更新的是每一位的个数和。这样，就能保证线段树区间更新的速率了。

具体看一下代码（学院派还是很好懂的）

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int maxN = 100005;
int N, M, op, L, R, Xi;
ll tree[maxN<<2][25], lazy[maxN<<2], ans;
void pushup(int rt)
{
    for(int i=0; i<22; i++)
    {
        tree[rt][i] = tree[rt<<1][i] + tree[rt<<1|1][i];
    }
}
void buildTree(int rt, int l, int r)
{
    lazy[rt] = 0;
    if(l == r)
    {
        ll x;  scanf("%lld", &x);
        for(int i=0; i<22; i++)
        {
            if( ((x>>i)&1) ) tree[rt][i] = 1;
            else tree[rt][i] = 0;
        }
        return;
    }
    int mid = (l + r)>>1;
    buildTree(rt<<1, l, mid);
    buildTree(rt<<1|1, mid+1, r);
    pushup(rt);
}
void pushdown(int rt, int l, int r)
{
    int mid = (l + r)>>1;
    if(lazy[rt])
    {
        lazy[rt<<1|1] = lazy[rt<<1|1]^lazy[rt];
        lazy[rt<<1] = lazy[rt<<1]^lazy[rt];
        for(int i=0; i<22; i++)
        {
            int tmp = ( ((lazy[rt]>>i)&1) );
            if(tmp)
            {
                tree[rt<<1][i] = mid-l+1-tree[rt<<1][i];
                tree[rt<<1|1][i] = r-mid-tree[rt<<1|1][i];
            }
        }
        lazy[rt] = 0;
    }
}
void update(int rt, int l, int r, int ql, int qr, int val)
{
    int mid = (l + r)>>1;
    if(ql<=l && qr>=r)
    {
        lazy[rt] = (lazy[rt]^val);
        for(int i=0; i<22; i++)
        {
            int tmp = ( (val>>i)&1 );
            if(tmp == 1)
            {
                tree[rt][i] = r-l+1-tree[rt][i];
            }
        }
        return;
    }
    pushdown(rt, l, r);
    if(ql>mid) update(rt<<1|1, mid+1, r, ql, qr, val);
    else if(qr<=mid) update(rt<<1, l, mid, ql, qr, val);
    else
    {
        update(rt<<1|1, mid+1, r, mid+1, qr, val);
        update(rt<<1, l, mid, ql, mid, val);
    }
    pushup(rt);
}
void query(int rt, int l, int r, int ql, int qr)
{
    int mid = (l + r)>>1;
    if(ql<=l && qr>=r)
    {
        for(int i=0; i<22; i++)
        {
            ans += (ll)(1<<i)*tree[rt][i];
        }
        return;
    }
    pushdown(rt, l, r);
    if(ql>mid) query(rt<<1|1, mid+1, r, ql, qr);
    else if(qr<=mid) query(rt<<1, l, mid, ql, qr);
    else
    {
        query(rt<<1, l, mid, ql, mid);
        query(rt<<1|1, mid+1, r, mid+1, qr);
    }
}
int main()
{
    scanf("%d%d", &N, &M);
    buildTree(1, 1, N);
    while(M--)
    {
        scanf("%d", &op);
        if(op == 1)
        {
            scanf("%d%d", &L, &R);
            ans = 0;
            query(1, 1, N, L, R);
            printf("%lld\n", ans);
        }
        else
        {
            scanf("%d%d%d", &L, &R, &Xi);
            update(1, 1, N, L, R, Xi);
        }
    }
    return 0;
}