핵심 아이디어

<aside> 💡

같은 수를 짝수번 XOR하면 0을 XOR 한 것과 같고

홀수번 XOR하면 한번 XOR 한 것과 같다.

</aside>

코드

#include <bits/stdc++.h>
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
using namespace std;
typedef long long ll;

class Seg
{
    private:
        int n;
        vector<int> tree;
        vector<int> lazy;

        void prop(int node, int start, int end)
        {
            if(lazy[node] == 0) return;

            tree[node] ^= lazy[node]*((end-start+1)%2);

            if(start != end){
                int mid = start+end>>1;
                lazy[2*node] ^= lazy[node];
                lazy[2*node+1] ^= lazy[node];
            }

            lazy[node] = 0;
        }

        void upd(int node, int start, int end, int left, int right, int val)
        {
            prop(node, start, end);
            if(right<start || end<left) return;
            if(left<=start && end<=right){
                lazy[node] ^= val;
                prop(node, start, end);
                return;
            }

            int mid = start+end>>1;
            upd(2*node, start, mid, left, right, val);
            upd(2*node+1, mid+1, end, left, right, val);

            tree[node] = tree[2*node]^tree[2*node+1];
        }

        int qry(int node, int start, int end, int left, int right)
        {
            prop(node, start, end);
            if(right<start || end<left) return 0;
            if(left<=start && end<=right) return tree[node];

            int mid = start+end>>1;
            int l = qry(2*node, start, mid, left, right);
            int r = qry(2*node+1, mid+1, end, left, right);

            return l^r;
        }

    public:
        Seg(int n): n(n)
        {
            tree.resize(4*n);
            lazy.resize(4*n);
        }

        void upd(int left, int right, int val) {upd(1, 0, n-1, left, right, val);}
        int qry(int left, int right) {return qry(1, 0, n-1, left, right);}
};

signed main()
{
    FASTIO;
    int n, m;
    
    cin >> n;
    Seg seg(n);
    for(int i = 0; i<n; i++){
        int a; cin >> a;
        seg.upd(i, i, a);
    }

    cin >> m;
    for(int q = 0; q<m; q++){
        int c, i, j, k;
        cin >> c >> i >> j;
        if(c == 1){
            cin >> k;
            seg.upd(i, j, k);
        }
        else{
            cout << seg.qry(i, j) <<"\\n";
        }
    }
    
    return 0;
}