Submission #725669

#	Time	Username	Problem	Language	Result	Execution time	Memory
725669		MercubytheFirst	XORanges (eJOI19_xoranges)	C++14	100 / 100	537 ms	9936 KiB

xoranges

#include<iostream>
#include<vector>
using namespace std;


#define CDIV(a, b) (((a) + (b) - 1) / (b))
class ST{
    public:
    int n;
    vector<int>t, v;

    ST(int sz){
        n = sz;
        t.resize(4 * n);
        v.resize(n + 1);
    }

    void build(int node, int l, int r){
        if(l == r){
            t[node] = v[l];
            return;
        }
        int mid = (l + r)/2;
        build(node * 2, l, mid);
        build(node * 2 + 1, mid + 1, r);
        t[node] = t[node * 2] ^ t[node * 2 + 1];
    }

    int query(int node, int l, int r, int tl, int tr){
        if(l > r or r < tl or tr < l)return 0;
        if(tl <= l and r <= tr){
            return t[node];
        }
        int mid = (l + r)/2;
        int res = query(node * 2,l, mid, tl, tr) ^ query(node * 2 + 1, mid + 1, r, tl, tr);
        return res;
    }

    void update(int node, int l, int r, int idx, int val){
        if(l > r or r < idx or idx < l)return;
        if(l == r and idx == l){
            t[node] = val;
            return;
        }
        int mid = (l + r)/2;
        update(node * 2, l, mid, idx, val);
        update(node * 2 + 1, mid + 1, r, idx, val);
        t[node] = t[node * 2] ^ t[node * 2 + 1];
    }

};


int main(){
    //freopen("test.in", "r", stdin);
    //freopen("test.out", "w", stdout);
    int n, q;
    cin >> n >> q;
    int esz = n/2, osz = CDIV(n,2);
    ST even(esz), odd(osz);
    for(int i = 1; i <= n; ++i){
        if(i % 2){
            cin >> odd.v[i/2 + 1];
        }
        else cin >> even.v[i/2];
    }
    even.build(1, 1,esz);
    odd.build(1, 1, osz);

    while(q--){
        int qt;
        cin >> qt;
        if(qt == 1){
            int idx, val;
            cin >> idx >> val;
            if(idx % 2){
                odd.update(1, 1, osz, idx/2 + 1, val);
            }
            else{
                even.update(1, 1, esz, idx/2, val);
            }
        }
        else{
            int l, r;
            cin >> l >> r;
            if((r - l + 1) % 2 == 0){
                cout << 0 << endl;
                continue;
            }
            if(l & 1){
                cout << odd.query(1, 1, osz, l/2 + 1, r/2 + 1) << endl;
            }
            else{
                cout << even.query(1, 1, esz, l/2, r/2) << endl;
            }
        }
    }
}

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