Submission #593434

#	Time	Username	Problem	Language	Result	Execution time	Memory
593434		serkanrashid	XORanges (eJOI19_xoranges)	C++14	100 / 100	138 ms	11236 KiB

xoranges

#include <bits/stdc++.h>
#define endl '\n'

using namespace std;

const int maxn=2*1e5+5;
int n,q;
int a[maxn],chet[4*maxn],nech[4*maxn];
int ql,qr,val;

void make_tree_chet(int v, int l, int r)
{
    if(l==r)
    {
        if(r%2==0) chet[v]=a[r];
        return;
    }
    int mid=(l+r)/2;
    make_tree_chet(v*2+0,l,mid+0);
    make_tree_chet(v*2+1,mid+1,r);
    chet[v]=chet[v*2]^chet[v*2+1];
}

void make_tree_nech(int v, int l, int r)
{
    if(l==r)
    {
        if(r%2==1) nech[v]=a[r];
        return;
    }
    int mid=(l+r)/2;
    make_tree_nech(v*2+0,l,mid+0);
    make_tree_nech(v*2+1,mid+1,r);
    nech[v]=nech[v*2]^nech[v*2+1];
}

int query_chet(int v, int l, int r)
{
    if(l>qr||r<ql||l>r) return 0;
    if(l>=ql&&r<=qr) return chet[v];
    int mid=(l+r)/2;
    return query_chet(v*2+0,l,mid+0)^query_chet(v*2+1,mid+1,r);
}

int query_nech(int v, int l, int r)
{
    if(l>qr||r<ql||l>r) return 0;
    if(l>=ql&&r<=qr)
    {
        return nech[v];
        cout << nech[v] << " " << v << " " << l << " " << r << endl;
    }
    int mid=(l+r)/2;
    return query_nech(v*2+0,l,mid+0)^query_nech(v*2+1,mid+1,r);
}

void update_chet(int v, int l, int r)
{
    if(l>qr||r<ql||l>r) return;
    if(l>=ql&&r<=qr)
    {
        chet[v]=val;
        return;
    }
    int mid=(l+r)/2;
    update_chet(v*2+0,l,mid+0);
    update_chet(v*2+1,mid+1,r);
    chet[v]=chet[v*2]^chet[v*2+1];
}

void update_nech(int v, int l, int r)
{
    if(l>qr||r<ql||l>r) return;
    if(l>=ql&&r<=qr)
    {
        nech[v]=val;
        return;
    }
    int mid=(l+r)/2;
    update_nech(v*2+0,l,mid+0);
    update_nech(v*2+1,mid+1,r);
    nech[v]=nech[v*2]^nech[v*2+1];
}


void read()
{
    cin >> n >> q;
    for(int i=1;i<=n;i++)
    {
        cin >> a[i];
    }
    make_tree_chet(1,1,n);
    make_tree_nech(1,1,n);
    int ch,l,r,ind,stoy;
    for(int i=1;i<=q;i++)
    {
        cin >> ch;
        if(ch==1)
        {
            cin >> ind >> stoy;
            ql=ind;
            qr=ind;
            val=stoy;
            if(ind%2==0) update_chet(1,1,n);
            else update_nech(1,1,n);
        }
        else
        {
            cin >> l >> r;
            if((r-l+1)%2==0) cout << 0 << endl;
            else
            {
                ql=l;
                qr=r;
                if(l%2==0) cout << query_chet(1,1,n) << endl;
                else cout << query_nech(1,1,n) << endl;
                //cout << "**************************" << endl;
            }
        }
    }
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	read();
return 0;
}

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