【CF242E】Xor Segment

题目大意：给定一个长度为 N 的序列，支持两种询问，即：区间异或，区间求和。

题解：加深了对线段树的理解。

对于线段树维护的变量一定是易于 modify 的，对于查询的答案只需用维护的东西进行组合而成即可。

异或和加法不具有分配律，因此不能直接维护区间和。考虑开 32 棵线段树，第 i 棵线段树维护区间值二进制第 i 位 1 的个数，最后只需用 32 棵线段树对应区间 1 的个数去组合出区间和即可。

代码如下

#include <bits/stdc++.h>

#define ls(o) o<<1

#define rs(o) o<<1|1

#define fi first

#define se second

#define pb push_back

#define mp make_pair

#define all(x) x.begin(),x.end()

#define cls(a,b) memset(a,b,sizeof(a))

using namespace std;

typedef long long ll;

typedef pair<int,int> P;

const int dx[]={0,1,0,-1};

const int dy[]={1,0,-1,0};

const int mod=1e9+7;

const int inf=0x3f3f3f3f;

const int maxn=1e5+10;

const double eps=1e-6;

inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}

inline ll sqr(ll x){return x*x;}

inline ll fpow(ll a,ll b,ll c){ll ret=1%c;for(;b;b>>=1,a=a*a%c)if(b&1)ret=ret*a%c;return ret;}

inline ll read(){

    ll x=0,f=1;char ch;

    do{ch=getchar();if(ch=='-')f=-1;}while(!isdigit(ch));

    do{x=x*10+ch-'0';ch=getchar();}while(isdigit(ch));

    return f*x;

}

/*------------------------------------------------------------*/

int n,m,a[maxn];

struct node{int cnt;bool tag;}t[21][maxn<<2];

inline void pushup(int bit,int o){t[bit][o].cnt=t[bit][ls(o)].cnt+t[bit][rs(o)].cnt;}

inline void pushdown(int bit,int o,int l,int r){

    if(!t[bit][o].tag)return;

    int mid=l+r>>1;

    t[bit][ls(o)].cnt=mid-l+1-t[bit][ls(o)].cnt,t[bit][ls(o)].tag^=1;

    t[bit][rs(o)].cnt=r-mid-t[bit][rs(o)].cnt,t[bit][rs(o)].tag^=1;

    t[bit][o].tag=0;

}

void build(int bit,int o,int l,int r){

    if(l==r){

        if(a[l]>>bit&1)t[bit][o].cnt=1;

        else t[bit][o].cnt=0;

        return;

    }

    int mid=l+r>>1;

    build(bit,ls(o),l,mid),build(bit,rs(o),mid+1,r);

    pushup(bit,o);

}

void modify(int bit,int o,int l,int r,int x,int y){//certainly modify

    if(l==x&&r==y){

        t[bit][o].cnt=r-l+1-t[bit][o].cnt;

        t[bit][o].tag^=1;

        return;

    }

    int mid=l+r>>1;

    pushdown(bit,o,l,r);

    if(y<=mid)modify(bit,ls(o),l,mid,x,y);

    else if(x>mid)modify(bit,rs(o),mid+1,r,x,y);

    else modify(bit,ls(o),l,mid,x,mid),modify(bit,rs(o),mid+1,r,mid+1,y);

    pushup(bit,o);

}

int query(int bit,int o,int l,int r,int x,int y){

    if(l==x&&r==y)return t[bit][o].cnt;

    int mid=l+r>>1;

    pushdown(bit,o,l,r);

    if(y<=mid)return query(bit,ls(o),l,mid,x,y);

    else if(x>mid)return query(bit,rs(o),mid+1,r,x,y);

    else return query(bit,ls(o),l,mid,x,mid)+query(bit,rs(o),mid+1,r,mid+1,y);

}

void read_and_parse(){

    n=read();

    for(int i=1;i<=n;i++)a[i]=read();

    for(int i=20;~i;i--)build(i,1,1,n);

}

void solve(){

    m=read();

    while(m--){

        int opt=read();

        if(opt==1){

            int l=read(),r=read();

            ll sum=0;

            for(int i=0;i<=20;i++)sum+=(1LL<<i)*(ll)query(i,1,1,n,l,r);

            printf("%lld\n",sum);

        }else{

            int l=read(),r=read(),val=read();

            for(int i=20;~i;i--)if(val>>i&1)modify(i,1,1,n,l,r);

        }

    }

}

int main(){

    read_and_parse();

    solve();

    return 0;

}

巴特西

【CF242E】Xor Segment

最新文章

热门文章