제출 #752735

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
752735		MateiKing80	XORanges (eJOI19_xoranges)	C++14	55 / 100	513 ms	6140 KiB

xoranges

#include <iostream>

using namespace std;

long long v[200005];
long long aint1[200005];
long long aint2[200005];


void build1(long long poz, long long st, long long dr)
{
    if(st==dr)
    {
        aint1[poz]=v[2*st-1];
        return;
    }
    long long mid=(st+dr)/2;
    build1(2*poz,st,mid);
    build1(2*poz+1,mid+1,dr);
    aint1[poz]=(aint1[2*poz]^aint1[2*poz+1]);
}

void build2(long long poz, long long st, long long dr)
{
    if(st==dr)
    {
        aint2[poz]=v[2*st];
        return;
    }
    long long mid=(st+dr)/2;
    build2(2*poz,st,mid);
    build2(2*poz+1,mid+1,dr);
    aint2[poz]=(aint2[2*poz]^aint2[2*poz+1]);
}


void update1(long long poz, long long st, long long dr, long long a, long long b)
{
    if(st==dr)
    {
        aint1[poz]=b;
        return;
    }
    long long mid=(st+dr)/2;
    if(a<=mid)
        update1(2*poz,st,mid,a,b);
    else
        update1(2*poz+1,mid+1,dr,a,b);
    aint1[poz]=(aint1[2*poz]^aint1[2*poz+1]);
}

void update2(long long poz, long long st, long long dr, long long a, long long b)
{
    if(st==dr)
    {
        aint2[poz]=b;
        return;
    }
    long long mid=(st+dr)/2;
    if(a<=mid)
        update2(2*poz,st,mid,a,b);
    else
        update2(2*poz+1,mid+1,dr,a,b);
    aint2[poz]=(aint2[2*poz]^aint2[2*poz+1]);
}


long long query1(long long poz, long long st, long long dr, long long a, long long b)
{
    if(a<=st && dr<=b)
        return aint1[poz];
    long long mid=(st+dr)/2;
    if(b<=mid)
        return query1(2*poz,st,mid,a,b);
    if(mid<a)
        return query1(2*poz+1,mid+1,dr,a,b);
    return (query1(2*poz,st,mid,a,b)^query1(2*poz+1,mid+1,dr,a,b));
}

long long query2(long long poz, long long st, long long dr, long long a, long long b)
{
    if(a<=st && dr<=b)
        return aint2[poz];
    long long mid=(st+dr)/2;
    if(b<=mid)
        return query2(2*poz,st,mid,a,b);
    if(mid<a)
        return query2(2*poz+1,mid+1,dr,a,b);
    return (query2(2*poz,st,mid,a,b)^query2(2*poz+1,mid+1,dr,a,b));
}




int main()
{
    long long n,q;
    cin>>n>>q;
    for(long long i=1;i<=n;i++)
        cin>>v[i];
    build1(1,1,(n+1)/2);
    build2(1,1,n/2);
    for(long long i=0;i<q;i++)
    {
        long long cer,a,b;
        cin>>cer>>a>>b;
        if(cer==1)
        {
            if( (a%2) == 1)
                update1(1,1,(n+1)/2,a/2+1,b);
            else
                update2(1,1,n/2,a/2,b);
        }
        else
        {
            if((b-a)%2==1)
                cout<<0<<'\n';
            else if((a%2)==1)
                cout<<query1(1,1,(n+1)/2,a/2+1,b/2+1)<<'\n';
            else
                cout<<query2(1,1,n/2,a/2,b/2)<<'\n';
        }
    }
}

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