Submission #1205404

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205404		mehralii	XORanges (eJOI19_xoranges)	C++20	100 / 100	100 ms	13896 KiB

xoranges

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template <typename T>
using indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define int long long
#define pb push_back
#define ppb pop_back
#define pf push_front
#define ppf pop_front
#define eb emplace_back
#define ins insert
#define F first
#define S second
#define MAXN 1000005
#define LOG (int)log2(MAXN)+1

const int INF = 1e18;
const int MOD = 998244353;
const double EPS = 1e-8;

struct segTree{
	struct node{
		int xor1, xor2, len;
	};

	node Merge(node a, node b){
		node res;
		res.len = a.len+b.len;
		if(a.len&1){
			res.xor1 = a.xor1 ^ b.xor2;
			res.xor2 = a.xor2 ^ b.xor1;
		} else{
			res.xor1 = a.xor1 ^ b.xor1;
			res.xor2 = a.xor2 ^ b.xor2;
		}

		return res;
	}
	
	int sz;
	vector<node> tree;

    void init_lens(int x, int lx, int rx) {
        tree[x].len = rx - lx;
        if (rx - lx == 1) return;
        int m = (lx + rx) >> 1;
        init_lens(2*x+1, lx, m);
        init_lens(2*x+2, m, rx);
    }

	segTree(int n){
		sz = 1;
		while(sz<n) sz*=2;
		tree.assign(2*sz-1, {0, 0, 0});
		init_lens(0, 0, sz);
	}

	node get(int l, int r, int x, int lx, int rx){
		if(r<=lx || rx<=l) return {0, 0, 0};
		if(l<=lx && rx<=r) return tree[x];
		int m = (lx+rx)/2;
		node s1, s2;
		s1 = get(l, r, 2*x+1, lx, m);
		s2 = get(l, r, 2*x+2, m, rx);
		return Merge(s1, s2);
	}
	
	int get(int l, int r){
		return get(l, r, 0, 0, sz).xor1;
	}
	
	void set(int i, int v, int x, int lx, int rx){
		if(rx-lx==1){
			tree[x] = {v, 0, 1};
			return;
		}
		int m = (lx+rx)/2;
		if(i<m) set(i, v, 2*x+1, lx, m);
		else set(i, v, 2*x+2, m, rx);
		tree[x] = Merge(tree[2*x+1], tree[2*x+2]);
	}
	
	void set(int i, int v){
		set(i, v, 0, 0, sz);
	}
};

void solve(){
	int n, q;
	cin >> n >> q;
	segTree sg(n);
	for(int i = 0; i < n; i++){
		int x;
		cin >> x;
		sg.set(i, x);
	}
	int t, l, r;
	while(q--){
		cin >> t >> l >> r;
		--l;
		if(t==1){
			sg.set(l, r);
		} else{
			if(!((r-l)%2)){
				cout << "0\n";
				continue;
			}
			cout << sg.get(l, r) << '\n';
		}
	}
}

signed main() {
    ios_base::sync_with_stdio(0);  cin.tie(0);  cout.tie(0);
    int t = 1;
    //cin >> t;
	for(int i = 1; i <= t; i++){
		//cout << "Case " << i << ": ";
		solve();
	}
    return 0;
}

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