Submission #1251815

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251815		osmiyum	XORanges (eJOI19_xoranges)	C++20	100 / 100	215 ms	12932 KiB

xoranges

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define ins insert
#define mid ((start+end)/2)
using namespace std;
const int MOD=1e9+7;
const int INF=2e5+5;

int n,q;
int a[INF];
int b[INF];
int c[INF];
int tree[4*INF];
int tree2[4*INF];

inline void build(int node,int start,int end){
    if(start==end){
        tree[node]=b[start];
        return;
    }
    build(node*2,start,mid);
    build(node*2+1,mid+1,end);
    tree[node]=tree[node*2]^tree[node*2+1];
}

inline void update(int node,int start,int end,int x,int val){
    if(start>end || start>x || end<x)return;
    if(start==x && end==x){
        tree[node]=val;
        return;
    }
    update(node*2,start,mid,x,val);
    update(node*2+1,mid+1,end,x,val);
    tree[node]=tree[node*2]^tree[node*2+1];
}

inline int query(int node,int start,int end,int l,int r){
    if(start>end || start>r || end<l)return 0;
    if(start>=l && end<=r)return tree[node];
    return query(node*2,start,mid,l,r)^query(node*2+1,mid+1,end,l,r);
}

inline void build2(int node,int start,int end){
    if(start==end){
        tree2[node]=c[start];
        return;
    }
    build2(node*2,start,mid);
    build2(node*2+1,mid+1,end);
    tree2[node]=tree2[node*2]^tree2[node*2+1];
}

inline void update2(int node,int start,int end,int x,int val){
    if(start>end || start>x || end<x)return;
    if(start==x && end==x){
        tree2[node]=val;
        return;
    }
    update2(node*2,start,mid,x,val);
    update2(node*2+1,mid+1,end,x,val);
    tree2[node]=tree2[node*2]^tree2[node*2+1];
}

inline int query2(int node,int start,int end,int l,int r){
    if(start>end || start>r || end<l)return 0;
    if(start>=l && end<=r)return tree2[node];
    return query2(node*2,start,mid,l,r)^query2(node*2+1,mid+1,end,l,r);
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>q;
    for(int i=1;i<=n;i++){
       cin>>a[i];
       if(i%2)b[(i+1)/2]=a[i];
       if(i%2==0)c[i/2]=a[i];
    }
    build(1,1,n);
    build2(1,1,n);
    while(q--){
        int f;
        cin>>f;
        if(f==1){
            int a,b;
            cin>>a>>b;
            if(a%2){
                update(1,1,n,(a+1)/2,b);
            }
            else{
                update2(1,1,n,a/2,b);
            }
        }
        else{
            int a,b;
            cin>>a>>b;
            if((b-a)%2)cout<<0<<endl;
            else{
                if(a%2){
                    cout<<query(1,1,n,(a+1)/2,(b+1)/2)<<endl;
                }
                else{
                    cout<<query2(1,1,n,a/2,b/2)<<endl;
                }
            }
        }
    }
    return 0;
}

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