Submission #1261974

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261974		iordache_	XORanges (eJOI19_xoranges)	C++20	0 / 100	50 ms	4680 KiB

xoranges

#include <bits/stdc++.h>
#define pb push_back
#define int long long
using namespace std;
const int N=2e5+5;
int v[N];
struct AIB
{
    int n;
    vector<int> aib;
    void init(int _n) {n=_n;aib.resize(n+5);}
    void update(int i, int x)
    {
        while(i<=n)
        {
            aib[i]^=x;
            i+=i&(-i);
        }
    }
    int pref(int i)
    {
        if(i<1) return 0;
        if(i>n) i=n;
        int ans=0;
        while(i)
        {
            ans^=aib[i];
            i-=i&(-i);
        }
        return ans;
    }
    int query(int l, int r) {return pref(r)-pref(l-1);}
};
AIB aib[2];
signed main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n,q;
    cin>>n>>q;
    for(int i=1;i<=n;++i) cin>>v[i];
    aib[1].init((n+1)/2);
    aib[0].init(n/2);
    for(int i=1;i<=n;++i) aib[i&1].update((i+1)/2,v[i]);
    while(q--)
    {
        int op;cin>>op;
        if(op==1)
        {
            int poz,val;cin>>poz>>val;
            aib[poz&1].update((poz+1)/2,(v[poz]^val));
            v[poz]=val;
        }
        else
        {
            int l,r;cin>>l>>r;
            if((r-l+1)%2==0) {cout<<"0\n";continue;}
            cout<<aib[l&1].query((l+1)/2,(r+1)/2)<<'\n';
        }
    }
}

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