Submission #999736

#	Time	Username	Problem	Language	Result	Execution time	Memory
999736		LilPluton	XORanges (eJOI19_xoranges)	C++14	100 / 100	318 ms	14164 KiB

xoranges

#include <bits/stdc++.h>
// author : Pluton
#define OPT         ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int         ll
#define ll          long long
#define pb          push_back
#define arr         array
#define fi          first
#define se          second
#define rep(i,j,k)  for(int i = j; i <= k; ++i)
#define all(a)      a.begin(),a.end()
#define pii         pair<int,int>
using namespace std;
const int INF = 1e18;

struct BIT
{
    int n;
    vector<int> ft;
    void init(int N)
    {
        n = N + 5;
        ft.assign(n + 5, 0);
    }
    void add(int pos, int val)
    {
        for (pos = pos + 1; pos <= n; pos += pos & -pos) ft[pos] += val;
    }
    int get(int pos, int res = 0)
    {
        for (pos = pos + 1; pos > 0; pos -= pos & -pos) res += ft[pos];
        return res;
    }
};
const int N = 2e5 + 5;

struct tree{
    int t[N * 4];
    tree()
    {
        memset(t, 0, sizeof(t));
    }
    void update(int node,int l,int r,int pos,int val)
    {
        if(l == r)
        {
            t[node] = val;
            return;
        }
        int mid = (l + r) / 2;
        if(pos <= mid)  update(node * 2, l, mid, pos, val);
        else    update(node * 2 + 1, mid + 1, r, pos, val);
        t[node] = (t[node * 2] ^ t[node * 2 + 1]);
    }
    int getans(int node,int tl,int tr,int l,int r)
    {
        if(tr < l || tl > r)    return 0;
        if(l <= tl && tr <= r)  return t[node];
        int mid = (tl + tr) >> 1;
        return getans(node * 2, tl, mid, l, r) ^ getans(node * 2 + 1, mid + 1, tr, l, r);
    }
} seg1,seg2;

void _()
{
    int n, q;
    cin >> n >> q;
    for(int i = 1, x; i <= n; ++i)
    {
        cin >> x;
        if(i & 1)   seg1.update(1,1,n,i / 2 + 1, x);
        else    seg2.update(1,1,n,i / 2, x);   
    }
    while(q--)
    {
        int t,a,b;
        cin >> t >> a >> b;
        if(t == 1)
        {
            if(a & 1) seg1.update(1, 1, n, a / 2 + 1, b);
            else seg2.update(1, 1, n, a / 2, b);
        }
        else
        {
            int k = b - a + 1;
            if((b - a + 1) & 1)
            {
                if(a & 1)   cout << seg1.getans(1,1,n,a / 2 + 1, a / 2 + 1 + k / 2) << endl;
                else    cout << seg2.getans(1,1,n,a / 2, a / 2 + k / 2) << endl;
            }
            else
            {
                cout << 0 << endl;
            }
        }
    }

    
}

signed main()
{
    OPT
    int tc = 1;
    while(tc--)
    {
        _();
    }
}

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