Submission #673357

#	Time	Username	Problem	Language	Result	Execution time	Memory
673357		Hanksburger	XORanges (eJOI19_xoranges)	C++17	100 / 100	121 ms	9204 KiB

xoranges

#include <bits/stdc++.h>
using namespace std;
int seg1[400005], seg2[400005], a[200005];
void build1(int i, int l, int r)
{
    if (l==r)
    {
        seg1[i]=a[l*2-1];
        return;
    }
    int m=(l+r)/2;
    build1(i*2, l, m);
    build1(i*2+1, m+1, r);
    seg1[i]=seg1[i*2]^seg1[i*2+1];
}
void build2(int i, int l, int r)
{
    if (l==r)
    {
        seg2[i]=a[l*2];
        return;
    }
    int m=(l+r)/2;
    build2(i*2, l, m);
    build2(i*2+1, m+1, r);
    seg2[i]=seg2[i*2]^seg2[i*2+1];
}
void update1(int i, int l, int r, int y, int z)
{
    if (l==r)
    {
        seg1[i]=a[l*2-1]=z;
        return;
    }
    int m=(l+r)/2;
    y<=m?update1(i*2, l, m, y, z):update1(i*2+1, m+1, r, y, z);
    seg1[i]=seg1[i*2]^seg1[i*2+1];
}
void update2(int i, int l, int r, int y, int z)
{
    if (l==r)
    {
        seg2[i]=a[l*2]=z;
        return;
    }
    int m=(l+r)/2;
    y<=m?update2(i*2, l, m, y, z):update2(i*2+1, m+1, r, y, z);
    seg2[i]=seg2[i*2]^seg2[i*2+1];
}
int query1(int i, int l, int r, int ql, int qr)
{
    if (ql<=l && r<=qr)
        return seg1[i];
    int m=(l+r)/2, x=0;
    if (ql<=m && l<=qr)
        x^=query1(i*2, l, m, ql, qr);
    if (ql<=r && m<qr)
        x^=query1(i*2+1, m+1, r, ql, qr);
    return x;
}
int query2(int i, int l, int r, int ql, int qr)
{
    if (ql<=l && r<=qr)
        return seg2[i];
    int m=(l+r)/2, x=0;
    if (ql<=m && l<=qr)
        x^=query2(i*2, l, m, ql, qr);
    if (ql<=r && m<qr)
        x^=query2(i*2+1, m+1, r, ql, qr);
    return x;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, q;
    cin >> n >> q;
    for (int i=1; i<=n; i++)
        cin >> a[i];
    build1(1, 1, (n+1)/2);
    if (n>1)
        build2(1, 1, n/2);
    for (int i=1; i<=q; i++)
    {
        int x, y, z;
        cin >> x >> y >> z;
        if (x==1)
            y&1?update1(1, 1, (n+1)/2, (y+1)/2, z):update2(1, 1, n/2, y/2, z);
        else if ((z-y)&1)
            cout << 0 << '\n';
        else
            cout << ((z-y)&1?0:y&1?query1(1, 1, (n+1)/2, (y+1)/2, (z+1)/2):query2(1, 1, n/2, y/2, z/2)) << '\n';
    }
}

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