Submission #637414

#TimeUsernameProblemLanguageResultExecution timeMemory
637414ulianamalanyakXORanges (eJOI19_xoranges)C++14
100 / 100
130 ms11220 KiB
#include <bits/stdc++.h> using namespace std; #define endl "\n" #define INF 1e16 #define fi first #define se second #define pb push_back #define in insert #define speedup ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); typedef long long ll; typedef long double ld; typedef pair<ll,ll> pll; //--------------------------------| const int DIM=2e5+7; ll n,m,k,l,r,q,t; ll a[DIM]; ll Tf[4*DIM]; ll Ts[4*DIM]; //--------------------------------| void buildf(ll l, ll r, ll v) { if (l==r) { if (l%2==0) { Tf[v]=0; } else { Tf[v]=a[l]; } return; } ll mid=(l+r)/2; buildf(l,mid,2*v+1); buildf(mid+1,r,2*v+2); Tf[v]=Tf[2*v+1]^Tf[2*v+2]; } void builds(ll l, ll r, ll v) { if (l==r) { if (l%2==1) { Ts[v]=0; } else { Ts[v]=a[l]; } return; } ll mid=(l+r)/2; builds(l,mid,2*v+1); builds(mid+1,r,2*v+2); Ts[v]=Ts[2*v+1]^Ts[2*v+2]; } void updf(ll tl, ll tr, ll v, ll pos, ll val) { if (pos>tr||pos<tl) return; if (tl==tr&&tl==pos) { Tf[v]=val; return; } ll mid=(tl+tr)/2; updf(tl,mid,2*v+1,pos,val); updf(mid+1,tr,2*v+2,pos,val); Tf[v]=Tf[2*v+1]^Tf[2*v+2]; } void upds(ll tl, ll tr, ll v, ll pos, ll val) { if (pos>tr||pos<tl) return; if (tl==tr&&tl==pos) { Ts[v]=val; return; } ll mid=(tl+tr)/2; upds(tl,mid,2*v+1,pos,val); upds(mid+1,tr,2*v+2,pos,val); Ts[v]=Ts[2*v+1]^Ts[2*v+2]; } ll fresf(ll tl, ll tr, ll v, ll l, ll r) { if (tl>r||tr<l) return 0; if (tl>=l&&tr<=r) return Tf[v]; ll mid=(tl+tr)/2; return fresf(tl,mid,2*v+1,l,r)^fresf(mid+1,tr,2*v+2,l,r); } ll fress(ll tl, ll tr, ll v, ll l, ll r) { if (tl>r||tr<l) return 0; if (tl>=l&&tr<=r) return Ts[v]; ll mid=(tl+tr)/2; return fress(tl,mid,2*v+1,l,r)^fress(mid+1,tr,2*v+2,l,r); } int main() { speedup; cin >> n >> q; for (int i=1;i<=n;i++) { cin >> a[i]; } buildf(1,n,0); builds(1,n,0); while(q--) { cin >> t; if (t==1) { cin >> k >> l; if (k%2==0) upds(1,n,0,k,l); else updf(1,n,0,k,l); } else { cin >> l >> r; if ((r-l+1)%2==0) cout << 0 << endl; else { if (l%2==1) cout << fresf(1,n,0,l,r) << endl; else cout << fress(1,n,0,l,r) << endl; } } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...