제출 #1097991

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1097991		omar1312	XORanges (eJOI19_xoranges)	C++17	0 / 100	62 ms	65536 KiB

xoranges

#include <bits/stdc++.h>
using namespace std;
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
#define ll long long
#define pb push_back
#define all(x) x.begin(), x.end()
const int mod = 1000000007;
const int N = 500005;
ll a[N/2+2];
ll tree[N+2][33][2];
ll ans[33];
void query(int node, int L, int R, int l, int r, bool odd){
	if(l > R || r < L)return;
	if(l >= L && r <= R){
		for(int j = 0; j < 32; j++)ans[j] += tree[node][j][odd];
		return;
	}
	ll mid = (l + r) / 2;
	return query(node * 2, L, R, l, mid, odd), query(node * 2 + 1, L, R, mid+1, r, odd);
}
void update(int ind, int node, int n){
	ll old = ind;
	old += n;
	for(int j = 0; j < 32; j++){
		if((1 << j) & a[ind])tree[old][j][ind % 2]--;
		if((1 << j) & node)tree[old][j][ind % 2]++;
	}
	a[ind] = node;
	old >>= 1;
	while(old){
		for(int j = 0; j < 32; j++){
			tree[old][j][ind % 2] = tree[old * 2][j][ind % 2] + tree[old * 2 + 1][j][ind % 2];
		}
		old >>= 1;
	}
	return;
}
void solve(){
	int n, q;
	cin>>n>>q;
	for(int i = 0; i < n; i++){
		cin>>a[i];
	}
	ll off = 1;
	while(off < n)off <<= 1;
	n = off;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < 32; j++){
			if((1 << j) & a[i])tree[i + n][j][i % 2]++;
		}
	}
	for(int i = n-1; i >= 0; i--){
		for(int j = 0; j < 32; j++){
			tree[i][j][0] = tree[i * 2][j][0] + tree[i * 2 + 1][j][0];
			tree[i][j][1] = tree[i * 2][j][1] + tree[i * 2 + 1][j][1];
		}
	}
	while(q--){
		int type;
		cin>>type;
		if(type == 1){
			int u, x;
			cin>>u>>x;
			--u;
			update(u, x, n);
		}
		else{
			int l, r;
			cin>>l>>r;
			--l;
			--r;
			query(1, 0, n-1, l, r, l % 2);
			ll out = 0;
			for(int j = 0; j < 32; j++){
				if(ans[j] & 1)out += (1 << j);
				// cout<<ans[j]<<' ';
				ans[j] = 0;
			}
			cout<<out<<'\n';
		}
	}
}
int main(){
cin.tie(0)->sync_with_stdio(0);
	int tt = 1;
	// cin>>tt;
	while(tt--){
		solve();
		cout<<'\n';
	}
}

• Subtask 1: 0 / 12
• Subtask 2: 0 / 18
• Subtask 3: 0 / 25
• Subtask 4: 0 / 20
• Subtask 5: 0 / 25