제출 #1188724

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1188724		mkkkkkkkk	XORanges (eJOI19_xoranges)	C++20	100 / 100	306 ms	11496 KiB

xoranges

#include <bits/stdc++.h>

using namespace std;

vector<long long> vec;
pair<long long,long long> tree[200000*4];

void build(long long node,long long l,long long r)
{
    if(l==r)
    {
        if(l%2==0)
        tree[node].first=vec[l];
        else
            tree[node].second=vec[l];
    }
    else
    {
        long long m=(l+r)/2;
        build(node*2+1,l,m);
        build(node*2+2,m+1,r);
        tree[node].first=tree[node*2+1].first^tree[node*2+2].first;
        tree[node].second=tree[node*2+1].second^tree[node*2+2].second;
    }
}

void qu(long long node,long long i,long long x,long long l,long long r)
{
    if(l==r)
    {
        vec[l]=x;
        if(l%2==0)
        tree[node].first=vec[l];
        else
            tree[node].second=vec[l];
    }
    else
    {
        long long m=(l+r)/2;
        if(i<=m)
            qu(node*2+1,i,x,l,m);
        else
            qu(node*2+2,i,x,m+1,r);
        tree[node].first=tree[node*2+1].first^tree[node*2+2].first;
        tree[node].second=tree[node*2+1].second^tree[node*2+2].second;

    }
}

long long ask(long long node,long long l,long long r,long long L,long long R)
{
    if(l>=L && r<=R)
    {

        if(L%2==0)
            return tree[node].first;
        else
            return tree[node].second;
    }
    else if(l>R || r<L)
    {

        return 0;
    }
    else
    {
        long long m=(l+r)/2;
        return ask(node*2+1,l,m,L,R)^ask(node*2+2,m+1,r,L,R);
    }
}


int main()
{
    long long n,q;
    cin>>n>>q;
    for(long long n1=n;n1>0;n1--)
    {
        long long x;
        cin>>x;
        vec.push_back(x);
    }
    build(0,0,vec.size()-1);
    for(;q>0;q--)
    {
        long long t;
        cin>>t;
        if(t==1)
        {
            long long i,x;
            cin>>i>>x;
            qu(0,i-1,x,0,vec.size()-1);
        }
        else
        {
            long long l,r;
            cin>>l>>r;
            if((r-l+1)%2==0)
                cout<<0<<endl;
            else
            cout<<ask(0,0,vec.size()-1,l-1,r-1)<<endl;
        }
    }

    return 0;
}

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