RT，感觉空间好像也不会爆？

#include<bits/stdc++.h>
#define int long long
using namespace std;
#define fi first
#define sc second
#define pii pair<int,int>
#define pb push_back
#define umap unordered_map
#define mset multiset
#define pq priority_queue
#define ull unsigned long long
#define i128 __int128
const int maxn=2e5+1;
const int mod=(1<<30);
struct node{
    int l,r,pos[2],tg;
    node operator +(node x){
        if(l==-1) return x;
        if(x.l==-1) return (*this);
        node res;
        res.l=l,res.r=x.r,res.tg=0;
        for(int i:{0,1}) res.pos[i]=min(pos[i],x.pos[i]);
        return res;
    }
    void rev(){
        swap(pos[0],pos[1]);
    }
    void debug(){
        cout<<l<<" "<<r<<" "<<pos[0]<<" "<<pos[1]<<" "<<tg<<endl;
    }
};
int ls(int u){
    return (u<<1);
}
int rs(int u){
    return (u<<1)|1;
}
bool ir(int L,int R,int l,int r){
    return (L<=l)&&(r<=R);
}
bool ofr(int L,int R,int l,int r){
    return (r<L)||(R<l);
}
struct SGT{
    node tr[maxn*4];
    void pushup(int u){
        if(tr[u].l==tr[u].r) return ;
        tr[u]=(tr[ls(u)]+tr[rs(u)]);
    }
    void build(int u,int l,int r,int *a){
        tr[u].l=l,tr[u].r=r,tr[u].tg=0;
        if(l==r) return tr[u].pos[a[l]]=l,tr[u].pos[!a[l]]=1e9,void();
        int mid=(l+r)>>1;
        build(ls(u),l,mid,a),build(rs(u),mid+1,r,a),pushup(u);
    }
    void pushdown(int u){
        if(tr[u].l==tr[u].r) return ;
        tr[u].tg=0;
        tr[ls(u)].tg^=1,tr[rs(u)].tg^=1;
        tr[ls(u)].rev(),tr[rs(u)].rev();
    }
    void upd(int u,int l,int r){
        if(tr[u].tg) pushdown(u);
        if(ir(l,r,tr[u].l,tr[u].r)) tr[u].tg^=1,tr[u].rev();
        else if(!ofr(l,r,tr[u].l,tr[u].r)) upd(ls(u),l,r),upd(rs(u),l,r),pushup(u);
    }
    int query(int u,int l,int r){
        if(tr[u].tg) pushdown(u);
        if(ir(l,r,tr[u].l,tr[u].r)) return tr[u].pos[1];
        else if(!ofr(l,r,tr[u].l,tr[u].r)) return min(query(ls(u),l,r),query(rs(u),l,r));
        else return 1e9;
    }
}t[30];
int n,q,a[maxn],b[maxn];
void solve(){
    cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=0;i<=29;i++){
        for(int j=1;j<=n;j++) b[j]=((a[j]>>i)&1);
        t[i].build(1,1,n,b);
    }
    while(q--){
        int op,x,y,z;
        cin>>op>>x>>y;
        if(op==1){
            cin>>z;
            for(int i=0;i<=29;i++){
                if(z&(1<<i)){
                    t[i].upd(1,x,y);
                }
            }
        }
        if(op==2){
            int res=0;
            for(int i=0;i<=29;i++){
                int p=t[i].query(1,x,y);
                if(p<=y) res=(res+(1ll<<i)*(y-p+1)%mod)%mod;
            }
            cout<<res<<endl;
        }
        // cout<<"-------"<<endl;
        // for(int i=1;i<n*2;i++) t[0].tr[i].debug();
        // cout<<"---"<<endl;
        // for(int i=1;i<n*2;i++) t[1].tr[i].debug();
        // cout<<"-------"<<endl;
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int t=1;
    // cin>>t;
    while(t--) solve();
    return 0;
}
/*
Samples
input:

output:

THINGS TODO:
检查freopen，尤其是后缀名
检查空间
检查调试语句是否全部注释
*/