문제 71
같은 수 쌍
길이가 $N$인 정수 수열 $A_1, A_2, \cdots, A_N$이 있다. $Q$개의 쿼리에 대해 구간 안에서 같은 값을 가진 순서쌍의 개수를 출력하라.
각 쿼리마다 $l \le i < j \le r$이면서 $A_i=A_j$인 순서쌍 $(i, j)$의 개수를 구해야 한다.
입력
첫 번째 줄에 두 정수 $N$, $Q$가 공백으로 구분되어 주어진다. $(1 \le N, Q \le 200\,000)$
두 번째 줄에 $N$개의 정수 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다. $(-10^9 \le A_i \le 10^9)$
세 번째 줄부터 $Q$개의 줄에 걸쳐 두 정수 $l$, $r$이 공백으로 구분되어 주어진다. $(1 \le l \le r \le N)$
출력
각 쿼리마다 조건을 만족하는 순서쌍의 개수를 한 줄에 하나씩 출력한다.
예제 입력 1
7 5 1 2 1 3 2 1 2 1 7 1 3 2 5 4 7 6 6
예제 출력 1
6 1 1 1 0
공식 해설
끝점 한 칸의 변화를 상수 시간에 처리하기
현재 구간에 값 $v$가 $c_v$개 있으면 같은 값의 쌍은 $\binom{c_v}{2}$개이다. $v$를 하나 넣으면 기존 $c_v$개와 새 쌍을 만들므로 답에 $c_v$를 더한 뒤 빈도를 늘린다. 제거할 때는 빈도를 먼저 줄이고 남은 빈도를 답에서 뺀다.
이 갱신으로 구간의 양 끝점을 한 칸씩 이동할 수 있다. 값의 범위가 넓으므로 먼저 좌표 압축하여 빈도를 배열에 저장한다.
질의 순서를 바꾸어 이동 줄이기
수열이 바뀌지 않고 질의가 독립적이므로 Mo's algorithm을 사용한다. 왼쪽 끝점을 길이 $B$의 블록으로 나누고, 먼저 왼쪽 블록 번호순으로, 같은 블록에서는 오른쪽 끝점순으로 질의를 정렬한다. 인접 블록마다 오른쪽 정렬 방향을 뒤집으면 불필요한 왕복도 줄일 수 있다.
빈 구간에서 시작해 각 질의의 양 끝점으로 이동하면서 빈도와 답을 갱신한다. 답은 원래 질의 번호에 저장하고 입력 순서대로 출력한다.
왼쪽 끝점의 총 이동은 $O(QB+N)$, 오른쪽 끝점의 총 이동은 $O(N^2/B+N)$이다. $B$를 $\sqrt N$ 정도로 두면 정렬을 포함한 시간복잡도는 $O(N\log(N+1)+Q\log(Q+1)+(N+Q)\sqrt N)$이고, 공간복잡도는 $O(N+Q)$이다. 답은 최대 $\binom{N}{2}$이므로 빈도 하나가 아니라 쌍의 개수 범위를 기준으로 누적한다.
구현 · 언어별 풀이
C++ 구현
압축용 배열을 sort와 unique로 정리하고 값의 인덱스를 구한다. 빈도는 int, 답은 long long으로 둔다. 추가에서는 현재 빈도를 답에 더한 뒤 증가시키고, 제거에서는 먼저 감소시킨 빈도를 답에서 뺀다. 질의 정렬 비교자는 블록 번호와 오른쪽 끝점을 비교한다.
C 구현
값을 정렬·압축하고 질의를 블록 번호와 오른쪽 끝점 순으로 정렬한다. 빈도는 int, 같은 값 쌍의 수는 long long이다. 추가 시 기존 빈도를 더하고 삭제 시 빈도를 먼저 줄인 뒤 뺀다.
압축된 값 x의 추가와 삭제는 다음과 같다.
ans += count[x];
count[x]++;
// x를 구간에서 제거할 때
count[x]--;
ans -= count[x];Python 구현
좌표 압축 후 정수 빈도 리스트를 둔다. 블록별로 오른쪽 끝점의 정렬 방향을 번갈아 하면 이동을 줄일 수 있다. 끝점을 옮길 때 빈도와 정수 답을 갱신한다.
압축된 값 x의 추가와 삭제는 다음과 같다.
answer += count[x]
count[x] += 1
# x를 구간에서 제거할 때
count[x] -= 1
answer -= count[x]Java 구현
int[] 빈도와 long 쌍 개수를 사용한다. 질의를 블록 번호와 오른쪽 끝점으로 정렬하고 원래 번호에 답을 저장한다. 삭제에서는 먼저 빈도를 감소시켜 남은 동일 값 개수만 빼야 한다.
압축된 값 x의 추가와 삭제는 다음과 같다.
ans += count[x];
count[x]++;
// x를 구간에서 제거할 때
count[x]--;
ans -= count[x];Rust 구현
빈도는 usize, 쌍 개수는 i64로 둔다. 쿼리를 블록 번호와 방향을 반영한 오른쪽 끝점 기준으로 정렬한다. 삭제 시 빈도를 먼저 줄인 뒤 답에서 뺀다.
압축된 값 x의 추가와 삭제는 다음과 같다.
answer += count[x] as i64;
count[x] += 1;
// x를 구간에서 제거할 때
count[x] -= 1;
answer -= count[x] as i64;JavaScript 구현
원소 값을 좌표 압축해 빈도를 Int32Array에 저장한다. 값 자체가 음수일 수 있으므로 값으로 배열을 바로 인덱싱하지 않는다. 정렬할 질의에는 왼쪽·오른쪽 끝점과 원래 번호를 보관한다.
질의 정렬의 비교 함수는 블록 번호와 오른쪽 끝점을 비교한 숫자를 반환한다. 같은 블록에서는 오른쪽 끝점의 정렬 방향을 번갈아 두면 포인터 이동을 줄일 수 있다.
function add(v) {
answer += count[v];
count[v]++;
}
function remove(v) {
count[v]--;
answer -= count[v];
}쌍의 개수는 최대 $\binom{200\,000}{2}$이므로 답은 Number로 둔다. $32$비트 배열에 답을 넣거나 answer | 0을 쓰면 값이 잘린다. 답은 원래 질의 번호에 저장해 입력 순서로 출력한다.