Submission #999700

#	Time	Username	Problem	Language	Result	Execution time	Memory
999700		vjudge1	XORanges (eJOI19_xoranges)	C++17	100 / 100	439 ms	7988 KiB

xoranges

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 1000000
struct Segtree{
    int n;
    vector<int> tr, ar;
    Segtree(int si){
        n = si;
        tr.assign(4 * n, 0);
    }
    void build(int v, int l, int r){
        if (l == r){
            tr[v] = ar[l];
        }
        else{
            int mid = (l + r) / 2;
            build(v * 2, l, mid);
            build(v * 2 + 1, mid + 1, r);
            tr[v] = tr[v * 2] ^ tr[v * 2 + 1];
        }
    }
    void update(int v, int l, int r, int pos, int nval){
        if (l == r){
            tr[v] = nval;
        }
        else{
            int mid = (l + r) / 2;
            if (pos <= mid){
                update(v * 2, l, mid, pos, nval);
            }
            else{
                update(v * 2 + 1, mid + 1, r, pos, nval);
            }
            tr[v] = tr[v * 2] ^ tr[v * 2 + 1];
        }
    }
    int query(int v, int l, int r, int ql, int qr){
        if (r < ql || l > qr){
            return 0;
        }
        else if (ql <= l && r <= qr){
            return tr[v];
        }
        else{
            int mid = (l + r) / 2;
            return query(v * 2, l, mid, ql, qr) ^ query(v * 2 + 1, mid + 1, r, ql, qr);
        }
    }
};
int main(){
    int n, a, q, ty, l, r;
    cin>>n>>q;
    Segtree sodd(n), seven(n);
    for (int i = 0; i < n; i++){
        cin>>a;
        if (i % 2 == 0){
            seven.update(1, 0, n - 1, i, a);
        }
        else{
            sodd.update(1, 0, n - 1, i, a);
        }
    }
    for (int i = 0; i < q; i++){
        cin>>ty>>l>>r;
        if (ty == 1){
            l--;
            if (l % 2 == 0){
                seven.update(1, 0, n - 1, l, r);
            }
            else{
                sodd.update(1, 0, n - 1, l, r);
            }
        }
        else{
            l--, r--;
            if ((r - l + 1) % 2 == 0){
                cout<<0<<"\n";
            }
            else{
                if (l % 2 == 0){
                    cout<<seven.query(1, 0, n - 1, l, r);
                }
                else{
                    cout<<sodd.query(1, 0, n - 1, l, r);
                }
                cout<<"\n";
            }
        }
    }
}

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