제출 #446720

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
446720		BT21tata	XORanges (eJOI19_xoranges)	C++17	100 / 100	183 ms	9160 KiB

xoranges

#include<bits/stdc++.h>
// #pragma GCC target ("avx,avx2,fma")
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
typedef long long ll;
typedef long double ld;
#define SPEED ios_base::sync_with_stdio(false); cin.tie(0), cout.tie(0)
#define rall(v) (v).rbegin(),(v).rend()
#define all(v) (v).begin(),(v).end()
#define OK cerr<<"OK"<<endl<<flush
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define F first
#define S second
#define y0 jahdakdh
#define y1 jahsadakdakdh
#define endl '\n'
using namespace std;
const ll MOD=1e9+7;
// mt19937 rng(std::chrono::system_clock::now().time_since_epoch().count());


int n, Q, a[200005], t1[400005], t2[400005];

void build1(int v, int l, int r)
{
    if(l==r)
    {
        t1[v]=a[(l<<1)-1];
        return;
    }
    int m=(l+r)>>1;
    build1(v<<1, l, m);
    build1(v<<1|1, m+1, r);
    t1[v]=t1[v<<1]^t1[v<<1|1];
}

void build2(int v, int l, int r)
{
    if(l==r)
    {
        t2[v]=a[l<<1];
        return;
    }
    int m=(l+r)>>1;
    build2(v<<1, l, m);
    build2(v<<1|1, m+1, r);
    t2[v]=t2[v<<1]^t2[v<<1|1];
}

void update1(int v, int l, int r, int pos, int x)
{
    if(l==r)
    {
        t1[v]=x;
        return;
    }
    int m=(l+r)>>1;
    if(pos<=m) update1(v<<1, l, m, pos, x);
    else update1(v<<1|1, m+1, r, pos, x);
    t1[v]=t1[v<<1]^t1[v<<1|1];
}

void update2(int v, int l, int r, int pos, int x)
{
    if(l==r)
    {
        t2[v]=x;
        return;
    }
    int m=(l+r)>>1;
    if(pos<=m) update2(v<<1, l, m, pos, x);
    else update2(v<<1|1, m+1, r, pos, x);
    t2[v]=t2[v<<1]^t2[v<<1|1];
}

int xor1(int v, int l, int r, int tl, int tr)
{
    if(tl<=l and r<=tr) return t1[v];
    if(r<tl or tr<l) return 0;
    int m=(l+r)>>1;
    return xor1(v<<1, l, m, tl, tr)^xor1(v<<1|1, m+1, r, tl, tr);
}

int xor2(int v, int l, int r, int tl, int tr)
{
    if(tl<=l and r<=tr) return t2[v];
    if(r<tl or tr<l) return 0;
    int m=(l+r)>>1;
    return xor2(v<<1, l, m, tl, tr)^xor2(v<<1|1, m+1, r, tl, tr);
}

int main()
{
    SPEED;
    cin>>n>>Q;
    for(int i=1; i<=n; i++)
        cin>>a[i];

    build1(1, 1, (n+1)>>1);
    build2(1, 1, n>>1);

    while(Q--)
    {
        int q, l, r;
        cin>>q>>l>>r;
        if(q==1)
        {
            if(l&1) update1(1, 1, (n+1)>>1, (l+1)>>1, r);
            else update2(1, 1, n>>1, l>>1, r);
        }
        else
        {
            if((r-l)&1) cout<<0<<endl;
            else
            {
                if(l&1) cout<<xor1(1, 1, (n+1)>>1, (l+1)>>1, (r+1)>>1)<<endl;
                else cout<<xor2(1, 1, n>>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