Submission #1273247

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273247		silence25	XORanges (eJOI19_xoranges)	C++20	100 / 100	356 ms	11268 KiB

xoranges

#include "bits/stdc++.h"
#define ll long long
using namespace std;
const ll maxn = 2*1e5+5;
ll n;
ll v[maxn];
ll oseg[4*maxn];
ll eseg[4*maxn];
void build(ll nd,ll s,ll e){
    if(s == e){
        oseg[nd] = v[s] * (s%2 == 1);
        eseg[nd] = v[s] * (s%2 == 0);
        return;
    }
    ll mid = s + (e-s)/2;
    build(2*nd,s,mid);
    build(2*nd+1,mid+1,e);
    oseg[nd] = (oseg[2*nd]^oseg[2*nd+1]);
    eseg[nd] = (eseg[2*nd]^eseg[2*nd+1]);
}
void update(ll nd,ll s,ll e,ll x){
    if(s > x || e < x){
        return;
    }
    if(s == e){
        oseg[nd] = v[s] * (s%2 == 1);
        eseg[nd] = v[s] * (s%2 == 0);
        return;
    }
    ll mid = s + (e-s)/2;
    update(2*nd,s,mid,x);
    update(2*nd+1,mid+1,e,x);
    oseg[nd] = (oseg[2*nd]^oseg[2*nd+1]);
    eseg[nd] = (eseg[2*nd]^eseg[2*nd+1]);
}
ll get(ll nd,ll s,ll e,ll l,ll r){
    if(s > r || e < l){
        return 0;
    }
    if(l <= s && e <= r){
        if(l%2){
            return oseg[nd];
        }else{
            return eseg[nd];
        }
    }
    ll mid = s + (e-s)/2;
    return (get(2*nd,s,mid,l,r) ^ get(2*nd+1,mid+1,e,l,r));
}
int main(){
    ll q;
    cin>>n>>q;
    for(ll i = 1;i<=n;i++){
        cin>>v[i];
    }
    build(1,1,n);
    while(q--){
        ll tp;
        cin>>tp;
        if(tp == 1){
            ll id,x;
            cin>>id>>x;
            v[id] = x;
            update(1,1,n,id);
        }else{
            ll l,r;
            cin>>l>>r;
            if((r-l+1)%2){
                cout<<get(1,1,n,l,r)<<endl;
            }else{
                cout<<0<<endl;
            }
        }
    }
}

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