11956번: OZLJEDA

https://www.acmicpc.net/problem/11956


$O(k+q)$

a1, a2, ..., ak, a1^...^ak k+1개의 항이 반복된다. 이 항들을 전부 xor시키면 0이 된다.
1~i 번 항의 누적 xor 배열을 만든 뒤 이를 이용해 각 쿼리마다 반복되지 않는 구간에 해당하는 항들의 xor 연산합을 구한다.

#include<cstdio>
int k, q;
long long a[100002], x, y;
int main() {
    scanf("%d", &k);
    for (int i = 1; i <= k; i++) scanf("%lld", a + i), a[i] ^= a[i - 1];
    k++;
    for (scanf("%d", &q); q--;)
        scanf("%lld %lld", &x, &y),
        printf("%lld\n", a[(y - 1) % k + 1] ^ a[(x - 2 + k) % k + 1]);
    return 0;
}