【按位建线段树】CF242 E

拼搏现实的明天。 2024-03-17 15:01 90阅读 0赞

[Problem - 242E - Codeforces][]

题意：

![d73c427a96b7413aa170d8e1b1cbd233.png][]

思路：

因为涉及到位运算操作，所以要在01矩阵内进行维护

每行都代表一个数，因此区间操作就是在两行之间的01矩阵操作

我们可以造20棵线段树，其中每一列01序列都对应着一棵线段树，一共20列

然后去看区间和怎么求，即一个01矩阵的贡献怎么求，我们可以按列算贡献

对于每一列的贡献，就是：(这一列的1的个数)\*(1<<j)，因此线段树就是去维护这一列1的个数

然后再看修改操作，修改是让所有数异或上某个值

体现在矩阵上，按位（列）去考虑

对于每一列，如果 x 为0，则不考虑取反

否则就是将这一列所有数都取反

这个修改操作对 这一列1的个数 有什么影响呢

就变成了 区间长度 - 这一列1的个数

因为是区间操作，我们需要维护一个tag，表示这个区间是否被取反

Pushup：

1的个数就是左右区间1的个数相加

Pushdown：

首先更新tag

然后更新cnt值，变为(r-l+1)-cnt

build：

一开始初始化序列为原来的样子

这样线段树就差不多想好了

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=1e5+10;
    const int mxe=1e5+10;
    const int mod=1e9+7;
    
    struct info{
    	int tag=0,cnt=0;
    	info(){}
    	info(int a):tag(a),cnt(a){}
    };
    
    info operator+(const info &l,const info &r){
    	info res;
    	res.cnt=l.cnt+r.cnt;
    	return res;
    }
    
    struct Segtree{
    	info val;
    }tree[mxe<<2][21];
    
    int N,Q,op,l,r,x;
    int a[mxn];
    
    void settag(int rt,int l,int r,int x){
    	tree[rt][x].val.tag^=1;
    	tree[rt][x].val.cnt=(r-l+1)-tree[rt][x].val.cnt;
    }
    void pushup(int rt,int x){
    	tree[rt][x].val=tree[rt<<1][x].val+tree[rt<<1|1][x].val;
    }
    void pushdown(int rt,int l,int r,int x){
    	if(tree[rt][x].val.tag!=0){
    		int mid=l+r>>1;
    		settag(rt<<1,l,mid,x);
    		settag(rt<<1|1,mid+1,r,x);
    		tree[rt][x].val.tag=0;
    	}
    }
    void build(int rt,int l,int r,int x){
    	if(l==r){
    		tree[rt][x].val.tag=0ll;
    		tree[rt][x].val.cnt=((a[l]&(1ll<<x))!=0);
    		return;
    	}
    	int mid=l+r>>1;
    	build(rt<<1,l,mid,x);
    	build(rt<<1|1,mid+1,r,x);
    	pushup(rt,x);
    }
    info query(int rt,int l,int r,int x,int y,int p){
    	if(x<=l&&r<=y){
    		return tree[rt][p].val;
    	}
    	pushdown(rt,l,r,p);
    	int mid=l+r>>1;
    	if(x>mid) return query(rt<<1|1,mid+1,r,x,y,p);
    	else if(y<=mid) return query(rt<<1,l,mid,x,y,p);
    	else{
    		return query(rt<<1,l,mid,x,y,p)+query(rt<<1|1,mid+1,r,x,y,p);
    	}
    }
    void modify(int rt,int l,int r,int x,int y,int k){
    	if(x<=l&&r<=y){
    		settag(rt,l,r,k);
    		return;
    	}
    	pushdown(rt,l,r,k);
    	int mid=l+r>>1;
    	if(x<=mid) modify(rt<<1,l,mid,x,y,k);
    	if(y>mid) modify(rt<<1|1,mid+1,r,x,y,k);
    	pushup(rt,k);
    }
    void solve(){
    	cin>>N;
    	for(int i=1;i<=N;i++) cin>>a[i];
    	for(int j=20;j>=0;j--) build(1,1,N,j);
    	cin>>Q;
    	while(Q--){
    		cin>>op;
    		if(op==1){
    			cin>>l>>r;
    			int res=0;
    			for(int j=20;j>=0;j--){
    				res+=query(1,1,N,l,r,j).cnt*(1ll<<j);
    			}
    			cout<<res<<'\n';
    		}else{
    			cin>>l>>r>>x;
    			for(int j=20;j>=0;j--){
    				if((x>>j)&1) modify(1,1,N,l,r,j);
    			}
    		}
    	}
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;//cin>>__;
    	while(__--)solve();return 0;
    }

[Problem - 242E - Codeforces]: https://codeforces.com/problemset/problem/242/E
[d73c427a96b7413aa170d8e1b1cbd233.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/1e378d05bea4443b8dfae1a70de8cb4b.png