제출 #448751

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
448751		UltraFalcon	XORanges (eJOI19_xoranges)	C++17	0 / 100	246 ms	21300 KiB

xoranges

#include <bits/stdc++.h>
#define int long long

using namespace std;

struct Segtree{
    int n;
    vector<pair<int, int>> data;

    Segtree(const vector<int>& v) {
        n = v.size();
        data = vector<pair<int, int>>(4*n);
        build(v, 1, 0, n);
    }

    public:
    void set(int i, int x) {
        set(i, x, 1, 0, n);
    }

    int get(int beg, int ed) {
        return get(beg, ed, 1, 0, n).first;
    }

    private:
    pair<int, int> get_data(pair<int, int> left, pair<int, int> right, int ll) { // ll = left length
        //cerr << "{" << left.first << " | " << left.second << "}, {" << right.first << " | " << right.second << "}\n";
        //cerr << ll << "\n";
        if (ll <= 0) {
            return right;
        } else if (ll % 2 == 0) {
            return make_pair(left.first ^ right.first, left.second ^ right.second);
        } else {
            return make_pair(left.first ^ right.second, left.second ^ right.first);
        }
    }

    void update(int pos, int ll) {
        data[pos] = get_data(data[pos*2], data[pos*2+1], ll);
    }

    void build(const vector<int>& v, int pos, int left, int right) {
        if (left+1 == right) {
            data[pos] = make_pair(v[left], 0);
        } else {
            int mid = (left + right) / 2;
            build(v, pos*2, left, mid);
            build(v, pos*2+1, mid, right);
            update(pos, mid-left);
        }
    }

    void set(int i, int x, int pos, int left, int right) {
        if (left+1 == right) {
            data[pos] = make_pair(x, 0);
        } else {
            int mid = (left + right) / 2;
            if (i < mid) {
                set(i, x, pos*2, left, mid);
            } else {
                set(i, x, pos*2+1, mid, right);
            }
            update(pos, mid-left);
        }
    }

    pair<int, int> get(int beg, int ed, int pos, int left, int right) {
        if (beg <= left && ed >= right) {
            return data[pos];
        } else if (beg >= right || ed <= left) {
            return make_pair(0, 0);
        } else {
            int mid = (left + right) / 2;
            return get_data(get(beg, ed, pos*2, left, mid),
                            get(beg, ed, pos*2+1, mid, right),
                            mid-beg);
        }
    }
};

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, q;
    cin >> n >> q;

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

    Segtree seg(a);

    for (int idx=0; idx<q; idx++) {
        int event;
        cin >> event;

        if (event == 1) {
            int i, j;
            cin >> i >> j;

            seg.set(i-1, j);
        } else {
            int l, u;
            cin >> l >> u;

            if ((l - u) % 2 == 1) {
                cout << 0 << "\n";
            } else {
                cout << seg.get(l-1, u) << "\n";
            }
        }
    }
}

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