제출 #1094012

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1094012		MrNanama	XORanges (eJOI19_xoranges)	C++17	100 / 100	307 ms	20576 KiB

xoranges

#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second

using namespace std;
using ll = long long;

template <typename T> ostream& operator<<(ostream& os, const vector<T>& vec){for (auto itr : vec){os << itr << " ";} return os;}

ll n,q;
vector<ll> arr;
vector<ll> odd;
vector<ll> even;

void upd(ll tar, ll val, vector<ll>& seg){
	ll ind = tar+n;

	seg[ind] = val;
	ind /= 2;

	while(ind){
		seg[ind] = seg[2*ind]^seg[2*ind+1];

		ind /= 2;
	}
}

ll get_val(ll tl, ll tr, vector<ll>& seg){
	ll lo = tl+n; ll hi = tr+n+1;
	ll ans = 0;

	while(lo < hi){
		if(lo & 1){ans ^= seg[lo]; lo++;}
		if(hi & 1){hi--; ans ^= seg[hi];}

		lo/=2; hi/=2;
	}

	return ans;
}

void solve(){
	cin >> n >> q;
	arr.resize(n);
	odd.assign(4*n, 0);
	even.assign(4*n, 0);

	for(ll i=0; i<n; i++){cin >> arr[i];}

	for(ll i=0; i<n; i++){
		if(i%2){
			upd(i,arr[i],odd);
		}else{
			upd(i,arr[i],even);
		}
	}

	for(ll quer=0; quer<q; quer++){
		ll opr;
		cin >> opr;

		if(opr == 1){
			ll tar, val;
			cin >> tar >> val;

			tar--;

			if(tar%2){upd(tar, val, odd);}
			else{upd(tar,val, even);}

		}else{
			ll l,r;
			cin >> l >> r;
			l--; r--;

			if(l % 2 != r % 2){
				cout << 0 << endl;
			}else{
				if(l % 2){
					cout << get_val(l, r, odd) << endl;
				}else{
					cout << get_val(l, r, even) << endl;
				}
			}
		}
	}
}

int main(){

	ios_base::sync_with_stdio(false); cin.tie(NULL);

	solve();
}

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