제출 #1179951

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1179951		mishasim	XORanges (eJOI19_xoranges)	C++20	100 / 100	83 ms	14408 KiB

xoranges

#include <iostream>

using namespace std;
#define endl '\n'

long long kof,n,q,k[200005],res,op,l,u,prp[200005],prnp[200005],t[800005],t1[800005];
void buildnp(int v, int tl, int tr)
{
if(tl==tr)
    {
    t[v] = prnp[tl];
    return;
    }
int tm = (tl+tr)/2;
buildnp(2*v+1,tl,tm);
buildnp(2*v+2,tm+1,tr);
t[v] = (t[2*v+1]^t[2*v+2]);
}

void buildp(int v, int tl, int tr)
{
if(tl==tr)
    {
    t1[v] = prp[tl];
    return;
    }
int tm = (tl+tr)/2;
buildp(2*v+1,tl,tm);
buildp(2*v+2,tm+1,tr);
t1[v] = (t1[2*v+1]^t1[2*v+2]);
}

void updatenp(int v, int tl, int tr, int pos, int val)
{
if(pos < tl || tr < pos) return;

if(tl==tr)
    {
    t[v] = val;
    return;
    }
int tm = (tl+tr)/2;
updatenp(2*v+1,tl,tm,pos,val);
updatenp(2*v+2,tm+1,tr,pos,val);
t[v] = (t[2*v+1]^t[2*v+2]);
}

void updatep(int v, int tl, int tr, int pos, int val)
{
if(pos < tl || tr < pos) return;

if(tl==tr)
    {
    t1[v] = val;
    return;
    }
int tm = (tl+tr)/2;
updatep(2*v+1,tl,tm,pos,val);
updatep(2*v+2,tm+1,tr,pos,val);
t1[v] = (t1[2*v+1]^t1[2*v+2]);
}

long long querynp(int v, int tl, int tr, int l, int r)
{
if(tl>r || tr<l)return 0;
if(tl>=l && tr<=r)return t[v];

int tm = (tl+tr)/2;
return (querynp(2*v+1,tl,tm,l,r)^querynp(2*v+2,tm+1,tr,l,r));
}

long long queryp(int v, int tl, int tr, int l, int r)
{
if(tl>r || tr<l)return 0;
if(tl>=l && tr<=r)return t1[v];

int tm = (tl+tr)/2;
return (queryp(2*v+1,tl,tm,l,r)^queryp(2*v+2,tm+1,tr,l,r));
}

int main()
{
    ios_base :: sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>q;

    kof = 0;
    if(n%2!=0)kof = 1;

    for(int i = 1 ; i<=n ; i++)
        {
        cin>>k[i];
        if(i%2==0)prp[i] = k[i];
        else prnp[i] = k[i];
        }

    buildp(0,1,n);
    buildnp(0,1,n);

    for(int i = 1 ; i<=q ; i++)
        {
        cin>>op>>l>>u;
        if(op==1)
            {
            if(l%2==0)updatep(0,1,n,l,u);
            else updatenp(0,1,n,l,u);
            }
        else
            {
            if(l%2==u%2)
                {
                if(u%2==0)
                    {
                    res = queryp(0,1,n,l,u);
                    }
                else res = querynp(0,1,n,l,u);
                }
            else res = 0;
            cout<<res<<endl;
            }
        }
    return 0;
}

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