二进制拆分线段树

noip 模拟20190907 T3 位运算（bit）

/*
reference:

translation:

solution:

trigger:

note:
    *
record:

date:
    2019.09.04
*/
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define dwn(i,a,b) for(int i=a;i>=b;--i)
template <typename T> inline void rd(T &x){x=0;char c=getchar();int f=0;while(!isdigit(c)){f|=c=='-';c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}x=f?-x:x;}
inline void write(int n){if(n==0)return;write(n/10);putchar(n%10+'0');}
#define mem(a,b) memset(a,b,sizeof(a))
#define ee(i,u) for(int i=head[u];i;i=e[i].next)

#define lson (o<<1)
#define rson (o<<1|1)
const int N=2e5+10,M=1e5+50,inf=0x3f3f3f3f;
int n,m,a[N],K[25];

struct tree{
    int l,r;
    int tg[25];bool val[25];
}t[N<<2];

inline void pushup(int o){
    rep(i,0,20)
        t[o].val[i]=t[lson].val[i]^t[rson].val[i];
}

inline void pushdown(int o,int l,int r){
    int mid=l+r>>1;
    rep(i,0,20){
        if(t[o].tg[i]==0)continue;
        if(t[o].tg[i]==1)
            t[lson].val[i]=t[rson].val[i]=0;
        else if(t[o].tg[i]==2)
            t[lson].val[i]=(mid-l+1)&1,t[rson].val[i]=(r-mid)&1;//区间赋为1 异或和:奇为1 偶为0
        t[lson].tg[i]=t[rson].tg[i]=t[o].tg[i];
        t[o].tg[i]=0;
    }
}

void And(int o,int l,int r,int x,int y){
    if(l>y||r<x) return;
    if(x<=l&&r<=y){
        rep(i,0,20)
            if(!K[i])
                t[o].val[i]=0,t[o].tg[i]=1;
        return;
    }
    pushdown(o,l,r);
    int mid=l+r>>1;
    And(lson,l,mid,x,y),And(rson,mid+1,r,x,y);
    pushup(o);
}

void Or(int o,int l,int r,int x,int y){
    if(l>y||r<x) return;
    if(x<=l&&r<=y){
        rep(i,0,20)
            if(K[i])
                t[o].val[i]=(r-l+1)&1,t[o].tg[i]=2;
        return;
    }
    pushdown(o,l,r);
    int mid=l+r>>1;
    Or(lson,l,mid,x,y),Or(rson,mid+1,r,x,y);
    pushup(o);
}

int Ans,ans[20];
void Xor(int o,int l,int r,int x,int y){
    if(l>y||r<x) return;
    if(x<=l&&r<=y){
        rep(i,0,20)
            ans[i]^=t[o].val[i];
        return;
    }
    pushdown(o,l,r);
    int mid=l+r>>1;
    Xor(lson,l,mid,x,y);
    Xor(rson,mid+1,r,x,y);
    pushup(o);
}
void print(int l,int r){
    Ans=0;
    mem(ans,0);
    Xor(1,1,n,l,r);
    rep(i,0,20)
        if(ans[i])
            Ans|=(1<<i);
    printf("%d\n",Ans);
}


inline void build(int o,int l,int r){
    t[o].l=l,t[o].r=r;
    if(l==r){
        rep(i,0,20)t[o].val[i]=(a[l]>>i)&1;
        return ;
    }
    int mid=l+r>>1;
    build(lson,l,mid);
    build(rson,mid+1,r);
    pushup(o);
}

int main(){
    #ifdef WIN32
    freopen("t3.txt","r",stdin);
    //freopen("and.out","w",stdout);
    #endif
    rd(n),rd(m);
    rep(i,1,n)rd(a[i]);
    build(1,1,n);
    while(m--){
        int op,x,y,k;
        rd(op);
        if(op==3) rd(x),rd(y),print(x,y);
        else{
            rd(x),rd(y),rd(k);
            rep(i,0,20)K[i]=(k>>i)&1;
            if(op==1) And(1,1,n,x,y);
            else if(op==2) Or(1,1,n,x,y);
        }
    }
    printf("%.3lf M",(double)sizeof(t)/(1<<20));
    return 0;
}

线段树+二进制位拆分【CF242E】XOR on Segment

/*
reference:

translation:

solution:
    由于异或不具有叠加性,所以不能用lazylazy标记直接异或。
    我们记录t[o].val[i]代表当前节点o,二进制位i上是1的数有多少个。
    由于,如果某一二进制位上原来为1,且当前异或的数x的二进制位上也有1,
    那么我们的当前t[o].val[i]=r-l+1-t[o].val[i]
    可以理解为01交换。
    然后由于2^20比10^6要大。所以只需要拆到20即可。
    然后直接计算即可。
trigger:

note:
    *
record:

date:
    2019.09.07
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define dwn(i,a,b) for(int i=a;i>=b;--i)
template <typename T> inline void rd(T &x){x=0;char c=getchar();int f=0;while(!isdigit(c)){f|=c=='-';c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}x=f?-x:x;}
inline void write(int n){if(n==0)return;write(n/10);putchar(n%10+'0');}
#define mem(a,b) memset(a,b,sizeof(a))
#define ee(i,u) for(int i=head[u];i;i=e[i].next)

#define lson (o<<1)
#define rson (o<<1|1)
const int N=1e5+10;

int n,m;

struct tree{
    int l,r;
    int tag,val[21];
}t[N<<2];

inline void pushup(int o){
    dwn(i,20,0)
        t[o].val[i]=t[lson].val[i]+t[rson].val[i];
}

inline void build(int o,int l,int r){
    t[o].l=l,t[o].r=r;
    if(l==r){
        int x;rd(x);
        dwn(i,20,0)
            if((x>>i)&1)
                t[o].val[i]=1;
        return ;
    }
    int mid=l+r>>1;
    build(lson,l,mid);
    build(rson,mid+1,r);
    pushup(o);
}

inline void pushdown(int o){
    if(t[o].tag==0)return ;
    int l=t[o].l,r=t[o].r;
    int mid=l+r>>1;
    dwn(i,20,0){
        if((t[o].tag>>i)&1){
            t[lson].val[i]=mid-l+1-t[lson].val[i];
            t[rson].val[i]=r-mid-t[rson].val[i];
        }
    }
    t[lson].tag^=t[o].tag;//继承
    t[rson].tag^=t[o].tag;
    t[o].tag=0;//清零
}

inline void change(int o,int x,int y,int k){
    int l=t[o].l,r=t[o].r;
    if(x<=l && r<=y){
        t[o].tag^=k;
        dwn(i,20,0)
            if((k>>i)&1)
                t[o].val[i]=r-l+1-t[o].val[i];
        return ;
    }
    pushdown(o);
    int mid=l+r>>1;
    if(x<=mid)change(lson,x,y,k);
    if(mid<y)change(rson,x,y,k);
    pushup(o);
}

inline int query(int o,int x,int y){
    int l=t[o].l,r=t[o].r;
    if(x<=l && r<=y){
        int res=0;
        dwn(i,20,0)
            res+=(1<<i)*t[o].val[i];
        return res;
    }
    pushdown(o);
    int mid=l+r>>1;
    int ans=0;
    if(x<=mid)ans+=query(lson,x,y);
    if(mid<y)ans+=query(rson,x,y);
    return ans;
}

signed main(){
    #ifdef WIN32
    freopen("CF242E.txt","r",stdin);
    #endif
    rd(n);
    build(1,1,n);
    rd(m);
    while(m--){
        int op,l,r,x;
        rd(op);
        if(op==1){
            rd(l),rd(r);
            printf("%lld\n",query(1,l,r));
        }
        else{
            rd(l),rd(r),rd(x);
            change(1,l,r,x);
        }
    }
//    printf("%.3lf M",(double)sizeof(t)/(1<<20));
    return 0;
}
/*
5
4 10 3 13 7
8
1 2 4
2 1 3 3
1 2 4
1 3 3
2 2 5 5
1 1 5
2 1 2 10
1 2 3
*/
/*
26
22
0
34
11
*/
/*
6
4 7 4 0 7 3
5
2 2 3 8
1 1 5
2 3 5 1
2 4 5 6
1 2 3
*/
/*
38
28
*/
/*
Description
给定一个长为n(n<=10^5)n(n<=10^5)的数组
数组里的数不超过10^6
有两种操作：
1:求sum[l,r];
2:对[l,r]中的所有数^x
Input
第一行一个整数nn,代表有一个长度为nn的数组。
第二行nn个整数,代表aiai
第三行为一个整数mm,代表有mm次操作。
接下来mm行每行描述一个操作。
Output
对于每一个操作11,输出一行代表sum[l,r]sum[l,r].
*/