문제 링크
- http://icpc.me/20062
문제 출처
- 2018 IOI Day1 2번
사용 알고리즘
- 세그먼트 트리
시간복잡도
- 풀이 참조
풀이
문제 요약
$N \times M$ 격자에 $0$부터 $NM-1$까지의 수가 하나씩 배정되어 있습니다. 아래와 같은 쿼리 $Q$개를 온라인으로 처리해야 합니다.
swap_seats(a, b): a와 b의 위치를 바꾼 뒤, $[0, K]$번의 위치가 직사각형을 이루는 $K$의 개수를 출력
$NM \leq 1\,000\,000 , Q \leq 50\,000$이며, 서브태스크와 각 서브태스크 별로 받을 수 있는 점수는 다음과 같습니다.
| 서브태스크 번호 | 조건 | 서브태스크 점수 | 포함 서브태스크 | 총 점수 |
|---|---|---|---|---|
| Subtask 1 | NM ≤ 100, Q ≤ 5’000 | 5점 | Subtask 1 | 5점 |
| Subtask 2 | NM ≤ 10’000, Q ≤ 5’000 | 6점 | Subtask 12 | 11점 |
| Subtask 3 | N ≤ 1’000, M ≤ 1’000, Q ≤ 5’000 | 20점 | Subtask 123 | 31점 |
| Subtask 4 | Q ≤ 5’000, $\vert a-b \vert$ ≤ 10’000 | 6점 | Subtask 124 | 17점 |
| Subtask 3+4 | - | - | Subtask 1234 | 37점 |
| Subtask 5 | N = 1 | 33점 | Subtask 5 | 33점 |
| Subtask 3+4+5 | - | - | Subtask 12345 | 70점 |
| Subtask 6 | 추가적인 제한 없음 | 30점 | Subtask 123456 | 100점 |
Subtask 1(5점): $O(N^2M^2Q)$
수 하나를 추가하고, 직사각형 형태인지 확인하는 과정을 Naive하게 구현하면 각 쿼리를 $O(N^2M^2)$에 처리할 수 있습니다.
Subtask 2(11점): $O(NMQ)$
$[0, K]$번이 직사각형을 이룬다는 것은 아래 식과 동치입니다. 이때 $r_1$, $r_2$, $c_1$, $c_2$는 각각 $R_i$의 Prefix Min/Max, $C_i$의 Prefix Min/Max입니다.
\[(r_2 - r_1 + 1)(c_2 - c_1 + 1) = K+1\]$R_i, C_i$의 Prefix Min/Max는 $O(NM)$에 구할 수 있으므로 각 쿼리를 $O(NMQ)$에 해결할 수 있습니다.
Subtask 3(31점): $O(NM + Q(N+M) \log (NM))$
몇 가지 관찰이 필요합니다.
관찰 1: 만들어질 수 있는 직사각형은 최대 $N+M$개
Proof: 가장 작은 직사각형의 크기는 $1 \times 1$, 가장 큰 직사각형의 크기는 $N \times M$이고, 직사각형이 바뀔 때마다 높이와 너비의 합이 1 이상 증가하므로 만들 수 있는 직사각형은 최대 $N+M$가지입니다.
관찰 2: $r_1, r_2, c_1, c_2$는 최대 $2(N+M)$번 변함
Proof: $R_i$로 가능한 값은 $N$가지, $C_i$로 가능한 값은 $M$가지입니다. 그러므로 $r_1, r_2$는 각각 최대 $N$번 변하고, $c_1, c_2$는 각각 최대 $M$번 변합니다.
관찰 3: $(R_x, C_x)$를 추가할 때, $[r_1, r_2] \times [c_1, c_2]$ 바깥에 있어야 Prefix Min/Max가 변함
Proof: 자명합니다.
관찰 1을 통해 실제로 $O(N+M)$개의 수만 확인해도 된다는 사실을 알 수 있습니다.
관찰 2를 통해, 관찰 3에서 언급하는 조건은 최대 $2(N+M)$번만 충족한다는 것을 알 수 있습니다.
새로운 수 $X$가 추가되는 상황을 두 가지로 분류해봅시다.
- $[r_1, r_2] \times [c_1, c_2]$에 포함되는 경우: Prefix Min/Max가 바뀌지 않습니다.
$(r_2 - r_1 + 1)(c_2 - c_1 + 1) = X+1$을 만족하는지만 확인하면 됩니다. - 그렇지 않은 경우: Prefix Min/Max를 갱신해야 합니다. 갱신한 뒤 직사각형 형태가 되는지 확인합니다.
지금까지 관찰한 것을 이용해, 세그먼트 트리를 이용하는 풀이를 생각할 수 있습니다.
$[s, e]$번에서의 $r_1, r_2, c_1, c_2$를 관리하는 세그먼트 트리를 만듭시다. 두 수의 위치를 바꾸는 것은 간단하게 처리할 수 있습니다.
정답을 구하는 함수 Query(node, s, e)는 위에서 분류한 2가지를 잘 구현하면 됩니다. 구체적으로, 아래와 같이 구현하면 됩니다.
- 정점이 관리하는 구간 $[s, e]$의 수들의 위치가 $[0, s)$에 포함되는 경우: $[0, e]$가 직사각형 형태인지 확인합니다.
- 현재 정점 $[s,e]$가 리프 노드($s=e$)인 경우: $[0, s]$가 직사각형 형태인지 확인합니다.
- 1, 2에 속하지 않는 경우:
return Query(node*2, s, m) + Query(node*2+1, m+1, e)
두 수를 교환하는 것은 $O(\log (NM))$에 처리할 수 있고, 정답을 구하는 Query 함수는 $O((N+M) \log (NM))$에 동작합니다. 그러므로 각 쿼리(swap_seats)를 $O((N+M) \log (NM))$에 처리할 수 있습니다.
Subtask 4(17점): $O(NM + \sum \vert a - b \vert)$
Subtask 2의 풀이를 조금만 변형하면 됩니다. $a$, $b$의 위치를 교환할 때 Prefix Min/Max가 바뀌는 위치는 $[a, b)$ 밖에 없습니다. 그러므로 각 쿼리를 $O(\vert a - b \vert)$에 처리할 수 있습니다.
Subtask 3+4(37점)
1 | |
Subtask 5(33점): $O(M + Q \log M)$
$[0, K]$가 직사각형 형태라면, 각 수가 등장한 위치를 기록한 배열 $V$는 0 0 ... 0 0 1 1 ... 1 1 0 0 ... 0 0꼴이 될 것입니다. $[0, K]$가 직사각형 형태인 것과 배열 $V$에서 인접한 두 원소가 다른 쌍의 개수가 2개인 것은 필요 충분 조건이라는 것을 알 수 있습니다. 또한, 배열 $V$에서 인접한 두 원소가 다른 쌍의 개수는 항상 2 이상입니다. 그러므로 최솟값과 최솟값의 개수를 빠르게 구할 수 있으면 문제를 해결할 수 있습니다.
구체적으로, $f(x)$를 다음과 같이 정의합시다.
- $\text{prev}(x) :=$ $(R_x, C_x) = (0, 0)$이거나 $(R_x, C_x-1)$에 있는 수가 $x$보다 크면 +1, 그렇지 않으면 -1
- $\text{next}(x) :=$ $(R_x, C_x) = (0, M-1)$이거나 $(R_x, C_x+1)$에 있는 수가 $x$보다 크면 +1, 그렇지 않으면 -1
- $f(x) := \text{prev}(x) + \text{next}(x)$
$f(x)$의 Prefix Sum의 최솟값이 2라면 정답은 2가 등장하는 횟수가 되고, 최솟값이 2가 아니라면 정답은 0이 됩니다.
전처리는 $O(M)$에 할 수 있고, 자리를 바꾸는 쿼리는 세그먼트 트리에 6번 업데이트를 하는 것으로 해결할 수 있습니다. ($(R_a, C_a-1), (R_a, C_a), (R_a, C_a+1), (R_b, C_b-1), (R_b, C_b), (R_b, C_b+1)$) 그러므로 각 쿼리를 $O(\log M)$에 처리할 수 있습니다.
Subtask 3+4+5(70점)
1 | |
Subtask 6(100점): $O(NM + Q \log (NM))$
Subtask 5를 통해 기하학적 관찰을 통한 문제 해결의 가능성을 보았습니다. 1차원에서의 풀이를 2차원으로 확장해봅시다. $[0, K]$가 직사각형 형태라면, 각 수가 등장한 위치를 기록한 행렬 $V$는 아래와 같은 형태를 갖습니다.
1 | |
모든 $2 \times 2$ 행렬 $\begin{pmatrix}(R_i, C_i) & (R_i, C_i+1) \ (R_i+1, C_i) & (R_i+1, C_i+1)\end{pmatrix}$에서, $1$이 1개 있는 행렬이 4개, $1$이 3개 있는 행렬이 0개 존재해야 한다는 것을 알 수 있습니다.
$1$이 1개 있는 행렬은 항상 4개 이상 존재하고, $1$이 3개 있는 행렬은 항상 0개 이상 존재합니다. 그러므로 Subtask 5의 풀이처럼 최솟값과 최솟값의 개수를 관리하는 세그먼트 트리를 사용해서 답을 구할 수 있습니다.
전처리는 Prefix Sum을 이용해 $O(NM)$에 할 수 있고, 두 수의 위치를 바꾸는 쿼리는 세그먼트 트리를 이용해 $O(\log (NM))$에 할 수 있습니다.