[STEP5] 0150 : 花匠

#include<stdio.h>
#include<string.h>
#define N 100001
#define M 20
int s[N],lazy[N*4]={0};
int add[N*4][M]={0};
void build(int root,int l,int r){
    int i,m=(l+r)/2;
    if(l==r){
        for(i=0;i<M;i++)
            add[root][i]=bool(s[l]&(1<<i));
        return;
    }
    build(root*2,l,m);
    build(root*2+1,m+1,r);
    for(i=0;i<M;i++)
        add[root][i]=add[root*2][i]+add[root*2+1][i];
}
void pushdown(int root,int l,int r){
    int i,m=(l+r)/2;
    //if(root*2+1<N){
        lazy[root*2]^=lazy[root];
        lazy[root*2+1]^=lazy[root];
        for(i=0;i<M;i++){
            if(lazy[root] & (1<<i)){
                add[root*2][i]=m-l+1-add[root*2][i];
                add[root*2+1][i]=r-m-add[root*2+1][i];
            }
        }
    //}
    lazy[root]=0;
}
void change(int root,int l,int r,int L,int R,int k){
    int i,m=(l+r)/2;
    if(r<L || l>R) return;
    if(L<=l && r<=R){
        for(i=0;i<M;i++){
            if(k & (1<<i)){
                add[root][i]=r-l+1-add[root][i];
            }
        }
        lazy[root]^=k;
        return;
    }
    pushdown(root,l,r);
    change(root*2,l,m,L,R,k);
    change(root*2+1,m+1,r,L,R,k);
    for(i=0;i<M;i++)
        add[root][i]=add[root*2][i]+add[root*2+1][i];
}
long long int cnt(int root,int l,int r,int L,int R){
    int i,m=(l+r)/2;
    long long int tmp=0;
    if(r<L || l>R) return 0;
    if(L<=l && r<=R){
        tmp=0;
        for(i=M-1;i>=0;i--){
            tmp=tmp*2+add[root][i];
        }
        return tmp;
    }
    pushdown(root,l,r);
    tmp=0;
    tmp+=cnt(root*2,l,m,L,R);
    tmp+=cnt(root*2+1,m+1,r,L,R);
    return tmp;
}
int main(){
    //freopen("1","r",stdin);
    int i,j,n,t,x,l,r,y;
    long long int ans;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d",&s[i]);
    build(1,1,n);
    scanf("%d",&t);
    while(t--){
        scanf("%d",&x);
        if(x==1){
            scanf("%d%d",&l,&r);
            ans=cnt(1,1,n,l,r);
            printf("%lld\n",ans);
        }
        else{
            scanf("%d%d%d",&l,&r,&y);
            change(1,1,n,l,r,y);
        }
    }
}