代码求条

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
const int mod = (1 << 30);
int n,q;
int a[N];
inline int ls(int x){
	return x << 1;
}

inline int rs(int x){
	return x << 1 | 1;
}
int Left;
struct segmenttree{
	int base;
	struct node{
		bool And,Or;
		bool tag;
	}tree[N << 2];
	inline void pushup(int p){
		tree[p].And = tree[ls(p)].And & tree[rs(p)].And;
		tree[p].Or = tree[ls(p)].Or | tree[rs(p)].Or;
	}
	inline void tag(int p){
		if(tree[p].And){
			tree[p].And = false;
			tree[p].Or = false;
		}else{
			if(!tree[p].Or){
				tree[p].And = true;
				tree[p].Or = true;
			}
		}
	} 
	inline void pushdown(int p){
		if(tree[p].tag){
			tree[ls(p)].tag = tree[rs(p)].tag = tree[p].tag;
			tag(ls(p)),tag(rs(p));
			tree[p].tag = false;
		}
	}
	void build(int p,int l,int r){
		if(l == r){
			tree[p].And = (a[l] >> base) & 1;
			tree[p].Or = (a[l] >> base) & 1;
			tree[p].tag = false;
			return; 
		}
		int mid = (l + r) >> 1;
		build(ls(p),l,mid);
		build(rs(p),mid + 1,r);
		pushup(p);
	}
	void query(int p,int l,int r,int ql,int qr){
//		cout << "query [" << ql << "," << qr << "] ==> " << tree[p].Or << '\n'; 
		if(ql > r || qr < l){
			Left = min(Left,(int)1e9);
			return;
		}
		int mid = (ql + qr) >> 1;
		if(ql == qr){
			Left = min(Left,ql);
			return;
		}
		pushdown(p);
		if(tree[ls(p)].Or == 1 && l <= mid) query(ls(p),l,r,ql,mid);
		else if(tree[rs(p)].Or == 1 && r > mid) query(rs(p),l,r,mid + 1,qr);
		return;
	}
	void update(int p,int l,int r,int ql,int qr){
//		cout << "update [" << ql << "," << qr << "] \n";
		if(ql > r || qr < l) return;
		if(ql >= l && qr <= r){
			tag(p);
			tree[p].tag = true;
			return;
		}
		pushdown(p);
		int mid = (ql + qr) >> 1;
		if(l <= mid) update(ls(p),l,r,ql,mid);
		if(r > mid) update(rs(p),l,r,mid + 1,qr);
		pushup(p);
	}
	void DEBUG(int p,int l,int r){
//		cout << "DEBUG " << p << " " << l << "," << r << '\n';
		if(l == r){
//			cout << tree[p].Or << " ";
			return;
		}
		pushdown(p);
		int mid = (l + r) >> 1;
		DEBUG(ls(p),l,mid);
		DEBUG(rs(p),mid + 1,r);
	}
	void Debug(){
		for(int i = 1;i <= (n << 1);i++){
			cout << tree[i].And << " ";
		}
	}
}Tree[31];
signed main(){
//	freopen("data.in","r",stdin);
//	freopen("my.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(nullptr),cout.tie(nullptr);
	cin >> n >> q;
	for(int i = 1;i <= n;i++){
		cin >> a[i];
	}
	for(int i = 0;i < 31;i++){
		Tree[i].base = i;
		Tree[i].build(1,1,n);
	}
	for(int i = 1;i <= q;i++){
		int opt;
		cin >> opt;
		if(opt == 1){
			int l,r,x;
			cin >> l >> r >> x;
			for(int j = 0;j < 31;j++){
				if((x >> j) & 1) Tree[j].update(1,l,r,1,n);
			}
		}else{
			int l,r;
			cin >> l >> r;
			long long ans = 0;
			for(int j = 0;j < 31;j++){
				Left = 1e9;
				Tree[j].query(1,l,r,1,n);
				int len;
				if(Left == 1e9) len = 0;
				else len = (r - Left + 1);
//				cout << " -" << Left << " -- \n";
				ans += (len * (1 << j));
				ans %= mod;
			}
			cout << ans << '\n';
		}
//		for(int j = 0;j < 31;j++){
//			cout << "-" << j << "-: ";
//			Tree[j].DEBUG(1,1,n);	
//			Tree[j].Debug();
//			cout << '\n';
//		}
	}
	return 0;
}
/*
8 30 11 14 11 11 17 9 15 4 0 1 0 18 14
8 30 11 14 11 11 17 9 8 3 0 1 0 18 14
8 30 11 14 11 11 17 9 8 3 0 1 0 18 14
8 30 11 14 11 11 17 9 8 3 0 1 0 18 14
8 30 11 14 11 11 17 9 8 3 0 1 0 18 14
8 30 1 4 1 1 27 9 8 3 0 1 0 18 14
8 30 1 4 1 1 24 10 11 3 0 1 0 18 14
8 30 1 4 1 1 24 12 13 3 0 1 0 18 14
8 30 1 4 1 14 23 3 2 3 0 1 0 18 14
8 30 1 4 1 14 23 3 2 3 0 1 0 18 14
8 30 1 3 6 9 16 4 5 4 7 1 0 18 14
*/
/*
0 0 1 0 1 1 1 1 0 1 0 1 0 0 0
0 1 1 1 1 1 0 0 0 1 0 0 0 1 1
0 1 0 1 0 0 0 0 0 0 0 0 0 0 1
1 1 1 1 1 1 0 1 1 0 0 0 0 0 1
0 1 0 0 0 0 1 0 0 0 0 0 0 1 0
8 30 11 14 11 11 17 9 8 3 0 1 0 18 14
8 30 11 14 11 11 17 9 8 3 0 1 0 18 14
*/