242-E 题目大意

给定一个长为\(n\)的数组\(a\)，\(q\)次操作，操作分两种：
\(1.l,r\)：输出\({\sum_{i=l}^{r}a_i}\)。
\(2.l,r,x\)：把区间\([l,r]\)中的元素都异或上\(x\)。

Solution

区间信息具有可并性，线段树能够快速得到所求区间的信息。

线段树节点中维护一个数组\(bit\)，\(bit[i]\)表示当前区间\([l,r]\)中有多少个元素第\(i\)为\(1\)，合并的过程把两个子节点的\(bit\)暴力合并即可。

操作二用懒标记维护即可，时间复杂度\(O(nlognlogU)\)，\(U\)为最大元素的二进制长度。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;

const int N=1e5+10;
struct node{
    int l,r,tag;
    vector<int> bit;
}tr[N<<2];

void pushup(int u){
    for(int i=22;~i;i--){
        tr[u].bit[i]=tr[u<<1].bit[i]+tr[u<<1|1].bit[i];
    }
}

void pushdown(int u){
    if(tr[u].tag){
        tr[u<<1].tag^=tr[u].tag;
        tr[u<<1|1].tag^=tr[u].tag;
        for(int i=22;~i;i--){
            if(tr[u].tag&(1<<i)){
                tr[u<<1].bit[i]=tr[u<<1].r-tr[u<<1].l+1-tr[u<<1].bit[i];
                tr[u<<1|1].bit[i]=tr[u<<1|1].r-tr[u<<1|1].l+1-tr[u<<1|1].bit[i];
            }
        }
        tr[u].tag=0;
    }
}

void build(int u,int l,int r,vector<int> &a){
    tr[u]={l,r,0};
    tr[u].bit.resize(23);
    if(l==r){
        for(int i=22;~i;i--){
            if(a[l-1]&(1<<i)){
                tr[u].bit[i]=1;
            }
        }
        return;
    }
    int m=(l+r)>>1;
    build(u<<1,l,m,a);
    build(u<<1|1,m+1,r,a);
    pushup(u);
}

void modify(int u,int l,int r,int k){
    if(l<=tr[u].l&&tr[u].r<=r){
        tr[u].tag^=k;
        for(int i=22;~i;i--){
            if(k&(1<<i)){
                tr[u].bit[i]=tr[u].r-tr[u].l+1-tr[u].bit[i];
            }
        }
        return;
    }
    pushdown(u);
    int m=(tr[u].l+tr[u].r)>>1;
    if(l<=m) modify(u<<1,l,r,k);
    if(r>m) modify(u<<1|1,l,r,k);
    pushup(u);
}

ll query(int u,int l,int r){
    if(l<=tr[u].l&&tr[u].r<=r){
        ll res=0;
        for(int i=22;~i;i--){
            res+=1LL*(1<<i)*tr[u].bit[i];
        }
        return res;
    }
    pushdown(u);
    ll res=0;
    int m=(tr[u].l+tr[u].r)>>1;
    if(l<=m) res+=query(u<<1,l,r);
    if(r>m) res+=query(u<<1|1,l,r);
    return res;
}

void solve(){
    int n;
    cin>>n;
    vector<int> a(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    build(1,1,n,a);
    int q;
    cin>>q;
    while(q--){
        int op,l,r,k;
        cin>>op>>l>>r;
        if(op&1){
            cout<<query(1,l,r)<<'\n';
        }else{
            cin>>k;
            modify(1,l,r,k);
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int T=1;
    //cin>>T;
    while(T--){
        solve();
    }
    return 0;
}