2020ICPC南京J

以前没写过势能线段树，然后错了114514个地方，我有罪。

#include<bits/stdc++.h>
using namespace std;
const int N=200013;
int a[N];
struct segtree{
#define mid ((l+r)>>1)
#define ls x<<1,l,mid
#define rs x<<1|1,mid+1,r
#define lc tr[x<<1]
#define rc tr[x<<1|1]
    struct info{
        int fi,fsz,se,c[32],xsm,tg;
    }tr[N<<2];
    void pu(int x){
        tr[x].xsm=lc.xsm^rc.xsm;
        for(int i=0;i<30;i++)tr[x].c[i]=lc.c[i]+rc.c[i];
        if(rc.fi>lc.fi)tr[x].fi=lc.fi,tr[x].fsz=lc.fsz,tr[x].se=min(lc.se,rc.fi);
        if(rc.fi<lc.fi)tr[x].fi=rc.fi,tr[x].fsz=rc.fsz,tr[x].se=min(rc.se,lc.fi);
        if(rc.fi==lc.fi)tr[x].fi=lc.fi,tr[x].fsz=lc.fsz+rc.fsz,tr[x].se=min(lc.se,rc.se);
    }
    void build(int x,int l,int r){
        tr[x].tg=-1;
        if(l==r){
            tr[x].xsm=tr[x].fi=a[l],tr[x].fsz=1;
            tr[x].se=(1<<30)-1;
            for(int i=0;i<30;i++)tr[x].c[i]=a[l]>>i&1;
            return;
        }
        build(ls),build(rs),pu(x);
    }
    void pd(int x){
        auto&t=tr[x].tg;
        if(t!=-1){
            if(lc.fi<t&&t<lc.se){
                for(int i=0;i<30;i++){
                    if(lc.fi>>i&1)lc.c[i]-=lc.fsz;
                    if(t>>i&1)lc.c[i]+=lc.fsz;
                }
                if(lc.fsz&1)lc.xsm^=lc.fi^t;
                lc.fi=lc.tg=t;
            }
            if(rc.fi<t&&t<rc.se){
                for(int i=0;i<30;i++){
                    if(rc.fi>>i&1)rc.c[i]-=rc.fsz;
                    if(t>>i&1)rc.c[i]+=rc.fsz;
                }
                if(rc.fsz&1)rc.xsm^=rc.fi^t;
                rc.fi=rc.tg=t;
            }
        }
        t=-1;
    }
    void add(int x,int l,int r,int L,int R,int val){
        if(L<=l&&R>=r){
            if(val<=tr[x].fi)return;
            else if(val<tr[x].se){
                for(int i=0;i<30;i++){
                    if(tr[x].fi>>i&1)tr[x].c[i]-=tr[x].fsz;
                    if(val>>i&1)tr[x].c[i]+=tr[x].fsz;
                }
                if(tr[x].fsz&1)tr[x].xsm^=tr[x].fi^val;
                tr[x].fi=tr[x].tg=val;
            }
            else pd(x),add(ls,L,R,val),add(rs,L,R,val),pu(x);
            return;
        }
        pd(x);
        if(L<=mid)add(ls,L,R,val);
        if(R>mid)add(rs,L,R,val);
        pu(x);
    }
    int qry(int x,int l,int r,int L,int R,int b){
        if(L<=l&&R>=r)return tr[x].c[b];
        int res=0;pd(x);
        if(L<=mid)res+=qry(ls,L,R,b);
        if(R>mid)res+=qry(rs,L,R,b);
        return res;
    }
    int qry(int x,int l,int r,int L,int R){
        if(L<=l&&R>=r)return tr[x].xsm;
        int res=0;pd(x);
        if(L<=mid)res^=qry(ls,L,R);
        if(R>mid)res^=qry(rs,L,R);
        return res;
    }
}T;

void work(){
    int n;cin>>n;
    int q;cin>>q;
    for(int i=1;i<=n;i++)cin>>a[i];
    T.build(1,1,n);
    for(int i=1,l,r,op,x;i<=q;i++){
        cin>>op>>l>>r>>x;
        if(op==1)T.add(1,1,n,l,r,x);
        else{
            int val=T.qry(1,1,n,l,r);
            if(val==x){
                cout<<0<<'\n';
                continue;
            }
            int xx=__lg(val^x);
            cout<<T.qry(1,1,n,l,r,xx)+(x>>xx&1)<<'\n';
        }
    }
}
int main(){
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout.tie(0);
    int T=1; //cin>>T
    while(T--) work();
    return 0;
}