BOJ 17943 : 도미노 예측

• 문제 링크 : boj.kr/17943
• 난이도 : G4
• 태그 : 누적합

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 987654321
#define int long long

using namespace std;

using ld = long double;
using pii = pair<int,int>;

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n, q;
    cin >> n >> q;
    vector<int> arr(n);
    for(int i = 1; i < n; i++) {
        cin >> arr[i];
        arr[i] ^= arr[i-1];
    }

    for(int i = 0; i < q; i++) {
        int s;
        cin >> s;
        if(s == 0) {
            int x, y;
            cin >> x >> y;
            cout << (arr[y-1]^arr[x-1]) << "\n";
        }
        if(s == 1) {
            int x, y, d;
            cin >> x >> y >> d;
            cout << (arr[y-1]^arr[x-1]^d) << "\n";
        }
    }
    

    return 0;
}

---

풀이

$(X_i \oplus X_{i+1}) \oplus (X_{i+1} \oplus X_{i+2}) = X_i \oplus X_{i+2}$이다. 따라서 누적합 배열을 이용하여 앞의 식을 확장하면 $ X_0 \oplus X_{i}$를 저장할 수 있다.

1번 질문에 대해서 $(X_0 \oplus X_{i}) \oplus (X_0 \oplus X_{j}) = X_{i} \oplus X_{j}$이다.

2번 질문에 대해서 $ X_{i} \oplus (X_{i} \oplus X_{j}) = X_{j}$이다.