题解 | #红球进黑洞#

思路：
因为没有关于异或的公式能对区间进行操作的
我们可以对于二进制的每一位都建一个线段树
对于每一位的区间我们是可以进行操作的
因为异或一个区间（区间中所有单点（叶子节点）的值是0或1）
这个区间的区间和就等于这个区间的长度减去原本的区间和
这样就能利用lazy对于每一位进行操作了
设 i 为左移了多少位
区间求和的时候就把答案加上每一位对应线段树的对应区间和乘上(1<<i)即可

AC代码：

#include <iostream>
#define mid (l+r>>1)
using namespace std;
typedef long long ll;
const int N=1e5+10;
struct node{
    ll sum,lazy;
}tree[21][N<<2];
ll a[N];
void build(int id,int l,int r,int root){
        if(l==r){
            tree[id][root].sum=((a[l]>>id)&1);
            return;
        }
        build(id,l,mid,root<<1);
        build(id,mid+1,r,root<<1|1);
        tree[id][root].sum=tree[id][root<<1].sum+tree[id][root<<1|1].sum;
        return;
}
void pushdown(int id,int l,int r,int root){
    if(tree[id][root].lazy==1){
        tree[id][root].lazy=0;
        tree[id][root<<1].lazy^=1;
        tree[id][root<<1|1].lazy^=1;
        tree[id][root<<1].sum=(mid-l+1)-tree[id][root<<1].sum;//异或的性质，区间里的1全部变成0,0全部变成了1
        tree[id][root<<1|1].sum=(r-mid)-tree[id][root<<1|1].sum;
    }
    return;
}
ll query(int id,int l,int r,int L,int R,int root){
    if(l>=L&&r<=R){
        return tree[id][root].sum;
    }
    pushdown(id,l,r,root);
    ll ans=0;
    if(L<=mid)ans+=query(id,l,mid,L,R,root<<1);
    if(R>mid)ans+=query(id,mid+1,r,L,R,root<<1|1);
    return ans;
}
void modify(int id,int l,int r,int L,int R,int root){
     if(l>=L&&r<=R){
        tree[id][root].sum=(r-l+1)-tree[id][root].sum;//异或后的区间和会变成区间长度减去原本的区间和
        tree[id][root].lazy^=1;
        return;
     }
    pushdown(id,l,r,root);
     if(L<=mid)modify(id,l,mid,L,R,root<<1);
     if(R>mid)modify(id,mid+1,r,L,R,root<<1|1);
     tree[id][root].sum=tree[id][root<<1].sum+tree[id][root<<1|1].sum;
     return;
}
int main()
{
    ios::sync_with_stdio(false);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=0;i<=20;i++){//因为数据1e5,开到20够了
        build(i,1,n,1);
    }
    while(m--){
        int op;
        cin>>op;
        if(op==1){
            ll ans=0;
            ll l,r;
            cin>>l>>r;
            for(int i=0;i<=20;i++){
                 ans+=1ll*query(i,1,n,l,r,1)*(1ll<<i);//注意long long
            }
            cout<<ans<<endl;
        }else{
            ll l,r,k;
            cin>>l>>r>>k;
            for(int i=0;i<=20;i++){
                if((k>>i)&1)modify(i,1,n,l,r,1);//因为一个数异或1的时候才会变，只看1就好了
            }
        }
    }
    return 0;
}