Submission #237704

#	Time	Username	Problem	Language	Result	Execution time	Memory
237704		RiscadoA	XORanges (eJOI19_xoranges)	C++14	100 / 100	541 ms	8696 KiB

xoranges

#include <bits/stdc++.h>

using namespace std;

int N, Q, A[200000];

class Tree {
public:
    void init(int offset) {
        this->offset = offset;
        if (N % 2 != 0) {
            this->sz = N / 2 + 1 - this->offset;    
        } else {
            this->sz = N / 2;
        }

        this->build(0, 0, this->sz - 1);
    }

    void update(int i, int value) {
        this->internal_update(i, value, 0, 0, this->sz - 1);
    }

    int query(int l, int r) {
        return this->internal_query(l, r, 0, 0, this->sz - 1);
    }

private:
    int build(int ni, int nl, int nr) {
        if (nl == nr) {
            this->data[ni] = A[2 * nl + this->offset];
        } else {
            int mid = nl + (nr - nl) / 2;
            this->data[ni] =
                this->build(2 * ni + 1, nl, mid) ^
                this->build(2 * ni + 2, mid + 1, nr);
        }

        return this->data[ni];
    }

    int internal_update(int i, int value, int ni, int nl, int nr) {
        if (nl > i || nr < i) {
            return this->data[ni];
        } else if (nl == nr) {
            this->data[ni] = value;
        } else {
            int mid = nl + (nr - nl) / 2;
            this->data[ni] =
                this->internal_update(i, value, 2 * ni + 1, nl, mid) ^
                this->internal_update(i, value, 2 * ni + 2, mid + 1, nr);
        }

        return this->data[ni];
    }

    int internal_query(int l, int r, int ni, int nl, int nr) {
        if (nl > r || nr < l) {
            return 0;
        } else if (nl >= l && nr <= r) {
            return this->data[ni];
        } else {
            int mid = nl + (nr - nl) / 2;
            return
                this->internal_query(l, r, 2 * ni + 1, nl, mid) ^
                this->internal_query(l, r, 2 * ni + 2, mid + 1, nr);
        }
    }

    int sz, offset;
    int data[4 * 100000];
};

Tree tree[2];

void rescan(int i, int j) {
    tree[i % 2].update(i / 2, j);
}

int query(int l, int u) {
    if ((u - l + 1) % 2 == 0) {
        return 0;
    }

    return tree[l % 2].query(l / 2, u / 2);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> N >> Q;

    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }

    for (int i = 0; i < 2; ++i) {
        tree[i].init(i);
    }

    for (int Qi = 0, action; Qi < Q; ++Qi) {
        cin >> action;
        if (action == 1) {
            int i, j;
            cin >> i >> j;
            rescan(i - 1, j);
        } else if (action == 2) {
            int l, u;
            cin >> l >> u;
            cout << query(l - 1, u - 1) << endl;
        }
    }
}

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