제출 #1176773

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1176773		chikien2009	XORanges (eJOI19_xoranges)	C++20	18 / 100	1095 ms	6472 KiB

xoranges

#include <bits/stdc++.h>

using namespace std;

void setup()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

class SEGMENT_TREE
{
    private:
    int tree_size;
    vector<pair<int, int>> tree;

    inline void Set(int ind, int l, int r, int x, int y)
    {
        if (r < x || y < l)
        {
            return;
        }
        if (l == r)
        {
            tree[ind] = {y * (l & 1), y * !(l & 1)};
            return;
        }
        int m = (l + r) >> 1;
        Set(ind << 1, l, m, x, y);
        Set(ind << 1 | 1, m + 1, r, x, y);
        tree[ind].first = tree[ind << 1].first ^ tree[ind << 1 | 1].first;
        tree[ind].second = tree[ind << 1].second ^ tree[ind << 1 | 1].second;
    }
    inline pair<int, int> Get(int ind, int l, int r, int x, int y)
    {
        if (r < x || y < l)
        {
            return {0, 0};
        }
        if (x <= l && r <= y)
        {
            return tree[ind];
        }
        int m = (l + r) >> 1;
        pair<int, int> p1 = Get(ind << 1, l, m, x, y);
        pair<int, int> p2 = Get(ind << 1 | 1, m + 1, r, x, y);
        return {p1.first ^ p2.first, p1.second ^ p2.second};
    }
    public:
    inline SEGMENT_TREE(int new_size)
    {
        tree_size = new_size;
        tree.clear();
        tree.resize(tree_size << 2, {0, 0});
    }
    inline void Set(int x, int y)
    {
        Set(1, 1, tree_size, x, y);
    }
    inline pair<int, int> Get(int x, int y)
    {
        return Get(1, 1, tree_size, x, y);
    }
} st(200000);

int n, q, a, b, c;
pair<int, int> x, y;

int main()
{
    setup();

    cin >> n >> q;
    for (int i = 1; i <= n; ++i)
    {
        cin >> a;
        st.Set(i, a);
    }
    while (q--)
    {
        cin >> b;
        if (b == 1)
        {
            cin >> b >> c;
            st.Set(b, c);
        }
        else
        {
            cin >> b >> c;
            a = (b + c) >> 1;
            x = st.Get(b, a);
            y = st.Get(a + 1, c);
            if (!(b & 1))
            {
                swap(y.first, y.second);
                swap(x.first, x.second);
            }
            cout << ((c - b + 1) & 1 ? (x.first ^ y.first) : 0) << "\n";
        }
    }
    return 0;
}

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