CF242E

• 给定 $n$ 个数的序列 $a$。$m$ 次操作，操作有两种：
  1. 求 $\displaystyle\sum_{i=l}^r a_i$。
  2. 把 $a_l\sim a_r$ 异或上 $x$。
• $1\le n\le 10^5$，$1\le m\le 5\times 10^4$，$0\le a_i\le 10^6$，$1\le x\le 10^6$。

思路

两年前做过的一题。

今天一看又忘了咋做的了。

然后看了看当初的代码。

由于 $0\le a_i\le 10^6$ ，不超过 $2^{20}$ ，再结合异或这个操作，所以考虑将每个数二进制拆位。

于是建立 $20$ 个线段树，分别维护每一位的 $01$ 情况 。

对于操作一，求区间和，将对应幂次累加起来即可。

对于操作二，将 $x$ 拆位，若该位为 $0$ 则无需操作，若为 $1$ 则区间取反即可。

代码

#include<bits/stdc++.h>
#define N 100010
#define M 25
#define ll long long 

using namespace std;

inline ll read() {
    ll w=1,x=0;
    char ch=0;
    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return w*x;
}

int n,m;
ll a[N],num[N][M];

class SegmentTree{
  private:
    ll sum[N<<2],lazy[N<<2];
    #define s(x) sum[x]
    #define l(x) lazy[x]
    #define ls (p<<1)
    #define rs (ls|1)
    #define mid (l+r>>1)
    void update(int p) {
        s(p)=s(ls)+s(rs);
    }
    void spread(int p,int l,int r) {
        if(!l(p)) return ;
        s(ls)=mid-l+1-s(ls),l(ls)^=l(p);
        s(rs)=r-mid-s(rs),l(rs)^=l(p);
        l(p)=0;
    }
  public:
    void build(int p,int l,int r,int x) {
        l(p)=0;
        if(l==r) {
            s(p)=num[l][x];
            return ;
        }
        build(ls,l,mid,x),build(rs,mid+1,r,x);
        update(p);
    }
    void Modify(int p,int l,int r,int L,int R) {
        if(l>R||r<L) return ;
        if(l>=L&&r<=R) {
            s(p)=r-l+1-s(p);
            l(p)^=1;
            return ;
        }
        spread(p,l,r);
        Modify(ls,l,mid,L,R),Modify(rs,mid+1,r,L,R);
        update(p);
    }
    ll ask(int p,int l,int r,int L,int R) {
        if(l>R||r<L) return 0;
        if(l>=L&&r<=R) return s(p);
        spread(p,l,r);
        return ask(ls,l,mid,L,R)+ask(rs,mid+1,r,L,R);
    }
}SMT[M];

void init() {
    for(int i=1;i<=n;i++) {
        int tmp=a[i],js=0;
        while(tmp) {
            num[i][js++]=tmp&1;
            tmp>>=1;
        }
    }
    for(int i=0;i<=20;i++) SMT[i].build(1,1,n,i);
}

int main() {
    n=read();
    for(int i=1;i<=n;i++) a[i]=read();
    m=read();

    init();
    for(int i=1;i<=m;i++) {
        int op,l,r,x;
        op=read(),l=read(),r=read();
        if(op==1) {
            ll ans=0;
            for(int j=0;j<=20;j++) ans+=(1ll<<j)*SMT[j].ask(1,1,n,l,r);
            printf("%lld\n",ans);
        }
        else {
            x=read();
            int js=0;
            while(x) {
                if(x&1) SMT[js].Modify(1,1,n,l,r);
                js++;
                x>>=1;
            }
        }
    }
    system("pause");
    return 0;
}