Submission #334038

#	Time	Username	Problem	Language	Result	Execution time	Memory
334038		limabeans	XORanges (eJOI19_xoranges)	C++17	100 / 100	194 ms	13596 KiB

xoranges

#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;


const int maxn = 1e6 + 5;


template<typename T> struct segtree {
    
    T merge(T x, T y) {
	return x^y;
    }
    int n;
    vector<T> t;
    void init(int n) {
	n += 10;
	this->n = n;
	t.assign(n*4, 0);
    }

    void upd(int v, int tl, int tr, int i, T dx) {
	if (tl == tr) {
	    t[v] = dx;
	} else {
	    int tm = (tl+tr)/2;
	    if (i<=tm) {
		upd(2*v,tl,tm,i,dx);
	    } else {
		upd(2*v+1,tm+1,tr,i,dx);
	    }
	    t[v] = merge(t[2*v], t[2*v+1]);
	}
    }

    T qry(int v, int tl, int tr, int l, int r) {
	if (l>tr || r<tl) {
	    return 0;
	}
	if (l <= tl && tr <= r) {
	    return t[v];
	}
	int tm = (tl+tr)/2;
	return merge(qry(2*v,tl,tm,l,r), qry(2*v+1,tm+1,tr,l,r));
    }
};


int n,q;
int a[maxn];
segtree<int> t[2];

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

    cin>>n>>q;
    t[0].init(n+10);
    t[1].init(n+10);
    
    for (int i=1; i<=n; i++) {
	cin>>a[i];
	t[i%2].upd(1,1,n,i,a[i]);
    }


    while (q--) {
	int op;
	cin>>op;
	if (op==1) {
	    int i,x;
	    cin>>i>>x;
	    a[i] = x;
	    t[i%2].upd(1,1,n,i,x);
	} else {
	    int l,r;
	    cin>>l>>r;
	    if (l%2!=r%2) {
		cout<<"0\n";
		continue;
	    }
	    int res = t[l%2].qry(1,1,n,l,r);
	    cout<<res<<"\n";	    
	}
    }
    
    
    return 0;
}

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