두 개의 덱

우선 쿼리 하나에 대한 답을 수학적으로 정리해 보자. 쿼리로 바닥 카드의 구간 $[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 구간 합 문제로 환원하는 것이다. $n \times n$ 격자 $G$가 있다고 하고, $r$행 $c$열의 칸을 $(r, c)$와 같이 나타내자. 처음에 모든 칸에 $0$이 적혀 있다고 가정한 뒤, 다음 규칙에 맞게 격자의 일부 칸을 수정한다.

• 모든 $1 \le i \le n$에 대해, 칸 $(i, i)$에 $1$을 더한다.
• $1 \le j < k \le n$이고 $a_j = a_k$이며 $a_{j+1}, \dots, a_{k-1}$이 모두 $a_j$와 다른 모든 $(j, k)$에 대해, 칸 $(j, k)$에서 $1$을 뺀다.

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

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

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

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

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

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