N개의 원소를 가진 배열 A가 주어졌을 때, 아래 조건을 만족하는 정수 쌍 (l, r)의 개수를 구하는 것이 이번 문제의 목표입니다.
A[l] XOR A[l+1] XOR ... XOR A[r] = A[l] + A[l+1] + ... + A[r]
예를 들어 입력 배열이 A = [2, 5, 4, 6]이라면 결과는 5입니다. 조건을 만족하는 쌍은 (1,1), (2,2), (3,3), (4,4), (1,2)로 총 5개이기 때문입니다.
문제 해결 접근 방법
이 문제는 누적 합(Prefix Sum), 누적 XOR(Prefix XOR) 배열과 이분 탐색(Binary Search)을 조합하면 O(N log N) 시간 복잡도로 효율적으로 해결할 수 있습니다.
핵심 아이디어
- s[i] : 첫 번째 원소부터 i번째 원소까지의 합
- sx[i] : 첫 번째 원소부터 i번째 원소까지의 XOR 값
- 구간 [l, r]의 합은 s[r] − s[l−1], 구간 [l, r]의 XOR은 sx[r] XOR sx[l−1]로 상수 시간에 계산할 수 있습니다.
- 여러 수의 XOR 값은 항상 그 수들의 합보다 작거나 같습니다. 따라서 l을 고정한 상태에서 r이 커질수록 '합 − XOR' 차이는 줄어들지 않고 단조롭게 유지됩니다.
- 즉, 어떤 지점에서 합이 XOR보다 커지면 그 이후에는 조건(합 = XOR)이 더 이상 성립하지 않습니다. 이 단조성 덕분에 각 l마다 조건을 만족하는 최대 r을 이분 탐색으로 찾을 수 있으며, l부터 해당 지점까지의 모든 r이 정답에 포함됩니다.
알고리즘 단계
n := 배열 A의 크기
크기가 (n + 1)인 배열 a, s, sx를 선언
i := 1부터 n까지 반복:
a[i] := A[i - 1]
s[i] := s[i - 1] + a[i]
sx[i] := sx[i - 1] XOR a[i]
res := 0
l := 1부터 n까지 반복:
bg := l, en := n, r := l
bg <= en인 동안 반복:
mi := (bg + en) / 2
만약 s[mi] - s[l - 1] == (sx[mi] XOR sx[l - 1])라면:
r := mi
bg := mi + 1
아니면:
en := mi - 1
res := res + (r - l + 1)
res 반환
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> A){
int n = A.size();
vector<int> a(n + 1), s(n + 1), sx(n + 1);
for (int i = 1; i <= n; i++){
a[i] = A[i - 1];
s[i] = s[i - 1] + a[i];
sx[i] = sx[i - 1] ^ a[i];
}
int res = 0;
for (int l = 1; l <= n; l++){
int bg = l, en = n, r = l;
while (bg <= en){
int mi = (bg + en) / 2;
if (s[mi] - s[l - 1] == (sx[mi] ^ sx[l - 1])){
r = mi;
bg = mi + 1;
}
else
en = mi - 1;
}
res += (r - l + 1);
}
return res;
}
int main(){
vector<int> A = { 2, 5, 4, 6 };
cout << solve(A) << endl;
}
실행 결과
입력:
{ 2, 5, 4, 6 }
출력:
5
결과 검증
- 길이 1인 구간 4개 : (1,1), (2,2), (3,3), (4,4) — 모두 자기 자신과의 합·XOR이 같으므로 성립
- (1,2) : 2 XOR 5 = 7, 2 + 5 = 7 → 성립
- (2,3) : 5 XOR 4 = 1, 5 + 4 = 9 → 불성립
- (3,4) : 4 XOR 6 = 2, 4 + 6 = 10 → 불성립
- 길이 3 이상의 구간 : 모두 합이 XOR보다 크므로 불성립
따라서 조건을 만족하는 쌍은 총 5개입니다.
시간 및 공간 복잡도
누적 배열 생성에 O(N), 각 l에 대한 이분 탐색에 O(log N)이 소요되므로 전체 시간 복잡도는 O(N log N)입니다. 공간 복잡도는 세 개의 누적 배열 저장을 위해 O(N)입니다.