Submission #1219837

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219837		khome	XORanges (eJOI19_xoranges)	C++20	75 / 100	179 ms	6484 KiB

xoranges

#include<bits/stdc++.h>
using namespace std;
// #define int long long

// const int INF = 1e18;
const int NEU = 0;

struct node {
    int el0, el1;
};

node make_node(int i1 = NEU, int i2 = NEU){
    node a; a.el0 = i1; a.el1 = i2;
    return a;
}

node merge(node i1, node i2){
    return (make_node(i1.el0^i2.el0, i1.el1^i2.el1));
}

struct SegTree {
    int n, N = 1;

    vector<node> tree;

    SegTree(vector<int> &a){
        n = a.size();

        while (N < n) N *= 2;

        tree.assign(2*N, make_node());
        for (int i = 0; i < n; i++) {
            if (i%2 == 0) tree[i+N] = make_node(a[i], 0);
            if (i%2 == 1) tree[i+N] = make_node(0, a[i]);

            // cout << tree[i+N]
        } 
        for (int i = N-1; i >= 1; i--) {
            tree[i] = merge(tree[i << 1], tree[(i << 1) + 1]);
        }
    }

    void update(int i, int x){

        node g;
        if (i%2 == 0) g = make_node(x, 0);
        if (i%2 == 1) g = make_node(0, x);

        i+=N;


        tree[i] = g;

        i >>= 1;

        while (i > 1){
            tree[i] = merge(tree[i << 1], tree[(i << 1) + 1]);

            i >>= 1;
        }
    }

    node get(int l, int r){
        node ans = make_node();
        int so = l % 2;
        l+=N; r+=N;

        while (l < r) {
            if (l & 1){
                ans = merge(ans, tree[l]);
                l++;
            }

            if (r & 1){
                r--;
                ans = merge(ans, tree[r]);
            }

            l >>= 1;
            r >>= 1;
        }
        return ans;
    }
};

void solve(){
    int n, q; cin >> n >> q;

    vector<int> v(n);
    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }

    SegTree sg(v);

    for (int i = 0; i < q; i++) {
        int p, l, r; cin >> p >> l >> r;
        if (p == 1){
            sg.update(l-1, r);
        }
        else {
            if ((r - l + 1) % 2 == 0) {cout << 0 << endl; continue;}
            if (l == r) {cout << v[l-1] << endl; continue;}
            l--; 
            if (l % 2 == 0) cout << sg.get(l, r).el0;
            if (l % 2 == 1) cout << sg.get(l, r).el1;
            cout << endl;
        }
    }

}

signed main(){
    ios::sync_with_stdio(0); cin.tie(0);
    int t = 1;

    // cin >> t;
    while(t--)solve();
}

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