두 개의 덱

우선 쿼리 하나에 대한 답을 수학적으로 정리해 보자. 쿼리로 바닥 카드의 구간 $[l_i, r_i]$가 들어왔다고 가정하자. 해당 범위 내에 $v$가 적힌 카드의 수를 $c_v$라 하고, 손 카드 중 $v$가 적힌 카드의 수를 $d_v$라 하자. 이때 해당 쿼리의 답을 아래와 같이 나타낼 수 있다.

$$\sum_{i=1}^n \min(c_i, d_i).$$

문제의 풀이에 대한 직관을 유도하기 위해, 더 쉬운 부분문제를 풀어보자. 모든 $d_i$가 $1$이라고 가정하자. 이때, 문제는 $Q$개의 구간 $[l_i, r_i]$에 대해 구간 내의 서로 다른 수의 개수를 구하는 문제가 된다. 이 문제를 해결하는 방법 중 하나는 문제를 2D 구간 합 문제로 환원하는 것이다. 격자 가 있다고 하고, 행 열의 칸을 와 같이 나타내자. 처음에 모든 칸에 이 적혀 있다고 가정한 뒤, 다음 규칙에 맞게 격자의 일부 칸을 수정한다.

• 모든 $1 \le i \le n$에 대해, 칸 $(i, i)$에 $1$을 더한다.
• $1 \le j < k \le n$이고 이며 이 모두 와 다른 모든 에 대해, 칸 에서 을 뺀다.

이때, 구간 $[l, r]$의 서로 다른 수의 개수는 $G$의 영역 $[l, n] \times [1, r]$의 모든 수의 합과 같다. 증명은 다음과 같다.

먼저 $(i, i)$ 꼴의 칸에 $1$을 더함으로써 생기는 영향은 $r-l+1$과 같다. 이는 구간 $[l, r]$에 있는 수의 개수와 같다. 하지만, 이때 같은 수가 여러 번 더해질 수 있으므로, 어떤 수 가 번 등장한다면, 만큼을 답에서 빼주어야 한다. 구간 에 가 번 등장하며 이라 하자. 등장하는 위치들을 오름차순으로 라 정의했을 때, 위의 격자 수정 규칙에 의해 칸 에 이 적혀 있어야 하며, 이 모든 칸들은 범위 내에 존재한다. 또한, 만약 인 에 의해 이 빼진 다른 격자칸들이 있다면, 해당 격자칸은 범위에 하나도 없음을 관찰할 수 있다. 따라서 값 에 의한 칸들의 총 기여량이 이 됨을 알 수 있고, 칸의 기여량과 상쇄되어 총 만큼의 기여를 하게 된다.

이제 원래 문제를 해결하는 방법을 알아보자. 두 번째 격자 수정 규칙을 다음과 같이 바꾼다.

• 모든 $1 \le x \le n$에 대해, $x$가 $v$번 등장하며, 그 위치를 오름차순으로 $i_1, i_2, \dots, i_v$라 하자. 인 모든 에 대해, 칸 에서 을 뺀다.

위 증명과 같은 논리를 적용하면, 범위 $[l, n] \times [1, r]$에서 $-1$ 칸들에 의한 값 $x$의 기여량이 $\min(c_x-d_x, 0)$임을 알 수 있다. (여기서 는 범위 에서 의 등장 횟수를 의미한다.) 칸이 총 만큼의 기여를 하므로, 두 기여를 더해 보면 값 의 합 기여량은 총 임을 알 수 있다. 따라서 위 풀이는 정당하다.

위 규칙으로 격자를 수정할 때, 격자 위에 $0$이 아닌 값을 가지는 칸이 최대 $2n$개이며, 이 칸들은 $O(n \log n)$ 전처리를 통해 구할 수 있다. 이후로는 2D에서 점들 $O(n)$개가 주어질 때, $O(q)$개의 직사각형 영역 합을 구하면 되고, 이는 오프라인 쿼리와 스위핑을 이용해 에 가능하다. 따라서, 전체 문제를 에 해결할 수 있다.