v[i] = a[1]^a[2]^a[3]^...a[i]라 하자. 이 때 i%4 == 3인 경우 v[i] 가 0이 된다!
또 a[l]^a[l+1]^...a[r-1]^a[r] = v[l-1]^v[r]이다.
이를 이용하면 쉽게 문제를 풀 수 있다.
#include <bits/stdc++.h>
using namespace std;
int solve(int x) {
int start = x/4*4;
int ret = start;
while (++start <= x) {
ret ^= start;
}
return ret;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while (t--) {
int a, b;
cin >> a >> b;
cout << (solve(a-1)^solve(b)) << '\n';
}
return 0;
}
누적합 느낌?