백준 27322번: 한별이의 퍼펙트 수열과 쿼리 교실 [C++]

작성일 | In
다이아몬드 III 다이아몬드 III

문제

한별이의 퍼펙트 수열과 쿼리 교실
구현량이 많은 느리게 갱신되는 세그먼트 트리 문제입니다.

풀이

벽 문제와 풀이가 일부 일치합니다.

문제는 우리에게 구간 최소, 구간 최대, 구간 합을 요구합니다. 따라서 세그먼트 트리의 노드에 min, max, sum을 저장해야 합니다. 또 최소, 최대, 덧셈 쿼리를 수행해야 하기에, 쿼리값을 저장해두는 lazyMin, lazyMax, lazyAdd가 필요합니다.
노드에 저장된 값들을 $m$(min), $M$(max), $S$(sum), 저장된 lazy 쿼리값들을 각각 $L_m$(lazyMin), $L_M$(lazyMax), $L_A$(lazyAdd)라 부르겠습니다.
그리고 새로 들어오는 쿼리는 $X_m$, $X_M$, $X_A$라 하겠습니다.
초기에 $L_m = \infty$, $L_M = -\infty$, $L_A = 0$입니다.

최소·최대

일단 덧셈 쿼리는 제쳐두고 최소·최대 쿼리를 수행하고 전파하는 법을 알아봅시다.

원래 배열에 저장된 값을 $a$라 하고, 여기에 lazy하게 저장된 쿼리값을 적용하려고 합니다.
이때 $L_M \leq L_m$인 경우, 쿼리의 순서가 영향을 미치지 않습니다. $L_M$을 먼저 적용해도 되고, $L_m$을 먼저 적용해도 됩니다.

증명

$a_1 = \min(\max(a, L_M), L_m)$, $a_2 = \max(\min(a, L_m), L_M)$으로 둡시다.

  1. $a \leq L_M$인 경우
    $a_1 = \min(L_M, L_m) = L_M$
    $a_2 = \max(a, L_M) = L_M$
  2. $L_M \leq a \leq L_m$인 경우
    $a_1 = \min(a, L_m) = a$
    $a_2 = \max(a_m, L_M) = a$
  3. $L_m \leq a$인 경우
    $a_1 = \min(a, L_m) = L_m$
    $a_2 = \max(L_m, L_M) = L_m$

따라서 무엇을 먼저 적용하든 상관없습니다.

우리는 새 쿼리값 $X_m$, $X_M$이 들어올 때 마다 $L_M \leq L_m$이 되도록 하려고 합니다.

먼저 $L_M \leq L_m$을 만족한다고 합시다. 여기서 최소 쿼리 $X_m$이 들어오는 경우, 배열의 값 $a$는 아래와 같이 바뀝니다.

\[\min(\min(\max(a, L_M), L_m), X_m)\]

분배 법칙을 이용해 다시 쓰면

\[\begin{align} &\min(\min(\max(a, L_M), X_m), \min(L_m, X_m)) \\ =&\min(\max(\min(a, X_m), \min(L_m, X_m)), \min(L_m, X_m)) \end{align}\]

여기서 $\min(a, X_m)$은 $\min(L_m, X_m)$이 있기 때문에 적용할 필요가 없습니다.
따라서 정리하면

\[\min(\max(a, \min(L_m, X_m)), \min(L_m, X_m))\]

$X_m$이 들어오면 $L_m = \min(L_m, X_m)$으로, $L_M = \min(L_M, X_m)$으로 바꿔주면 됩니다.
$X_M$에 대해서도 같은 방법을 이용하면 $L_m = \max(L_m, X_M)$, $L_M = \max(L_M, X_M)$으로 바꿔주면 됨을 알 수 있습니다.
이렇게 하면 항상 $L_M \leq L_m$ 입니다.

덧셈

$L_A$를 적용해 봅시다. 최소·최대 쿼리 이후에 덧셈 쿼리가 들어왔다면 단순히 더하기만 하면 됩니다.
덧셈 쿼리 이후에 최소·최대 쿼리가 들어온 경우를 생각해 봅시다.

\[\min(\max(a + L_A, X_M), X_m)\]

분배 법칙을 이용하면

\[\begin{align} &\min(\max(a + L_A, X_M), X_m) \\ =&\min(\max(a, X_M - L_A) + L_A, X_m) \\ =&\min(\max(a, X_M - L_A), X_m - L_A) + L_A \end{align}\]

덧셈 쿼리를 마지막에 수행하도록 순서를 바꿀 수 있습니다.
따라서 덧셈 쿼리 이후에 $X_m$, $X_M$이 들어오는 경우 $X_m - L_A$, $X_M - L_A$로 바꿔서 적용하면 됩니다.

중간 정리

항상 쿼리는 $\min(\max(a, L_M), L_m) + L_A$로 계산됩니다. 아래 노드로 전파하는 순서도 이와 같습니다.

  1. 최소 쿼리 $X_m$이 들어온 경우
    $L_m = \min(L_m, X_m - L_A)$, $L_M = \min(L_M, X_m - L_A)$으로 갱신합니다.
  2. 최대 쿼리 $X_M$이 들어온 경우
    $L_m = \max(L_m, X_M - L_A)$, $L_M = \max(L_M, X_M - L_A)$으로 갱신합니다.
  3. 덧셈 쿼리 $X_A$가 들어온 경우
    $L_A = L_A + X_A$로 갱신합니다.

$L_m$, $L_M$, $L_A$의 범위는 다음과 같습니다.

\[\begin{align} &L_m = \infty\ \text{or}\ L_m \leq 10 \\ &L_M = -\infty\ \text{or}\ L_M \leq 10 \\ &L_A \geq 0 \end{align}\]

값 계산

최소, 최대, 덧셈 쿼리를 적용하고 $m$, $M$, $S$를 계산해 봅시다.
$1 \leq X \leq 10$이라는 점을 이용하면 각 노드마다 $1 \leq i \leq 10$인 $i$의 개수를 저장해 두는 방식으로 계산할 수 있습니다.
이러한 $i$의 개수를 $cnt[i]$라 합시다.

최대, 최소, 덧셈 순서로 계산합니다. 최대·최소의 순서를 바꾸면 구현 방식이 달라질 수 있습니다.

최대

$1 \leq i \leq L_M$인 $i$에 대해

  1. $cnt[L_M]$에 $cnt[i]$를 더합니다.
  2. $S$에 $(L_M - i)cnt[i]$를 더합니다.
  3. $cnt[i] = 0$으로 갱신합니다.

$m = \max(m, L_M)$
$M = \max(M, L_M)$ 으로 갱신합니다.

최소

  1. $L_m \leq 0$인 경우
    1. $m = M = L_m$으로 갱신합니다.
    2. $S = (e - s + 1)L_m$으로 갱신합니다.
      여기서 $s, e$는 각각 노드가 담당하는 범위의 시작, 끝입니다. 따라서 $(e - s + 1)$은 노드가 담당하는 범위의 수의 개수를 뜻합니다.

  2. $1 \leq L_m \leq 10$인 경우

    1. $L_m$보다 큰 것의 개수 $g = (e - s + 1) - \sum\limits^{L_m-1}_{i = 1} cnt[i]$를 셉니다.
    2. $cnt[L_m]$에 $g$를 더합니다.
    3. $1 \leq i < L_m$인 $i$에 대해 $cnt[i] = 0$으로 갱신합니다.
    4. 배열의 모든 원소 $A_i$가 $1 \leq A_i \leq 10$이므로 $S = \sum\limits^{10}_{i=1} i\cdot cnt[i]$로 갱신합니다.
    5. $m = \min(m, L_m)$, $M = \min(M, L_m)$ 으로 갱신합니다.

덧셈

  1. $m \leq 0$인 경우
    모든 원소가 $m + L_A$가 됩니다.
    따라서 $m + L_A \leq 10$인 경우 $cnt[m + L_A] = (e - s + 1)$로 갱신합니다.
  2. 아닌 경우
    1. $1 \leq i \leq 10$이고 $10 < i + L_A$인 $i$에 대해 $cnt[i] = 0$으로 갱신합니다.
    2. $i = 10 - L_A$부터 $i$에 $1$씩 빼며 $i \geq 1$인 동안
      $cnt[i + L_A]$에 $cnt[i]$를 더하고 $cnt[i] = 0$으로 갱신합니다.

$m = m + L_A$
$M = M + L_A$
$S = S + (e - s + 1)L_A$ 로 갱신합니다.

갱신이 전부 끝나면 자식에게 전파한 후 $L_m$, $L_M$, $L_A$를 초기화하면 됩니다.

이외에는 평범한 느리게 갱신되는 세그먼트 트리와 비슷하게 구현하면 $O(M\log N)$으로 해결할 수 있습니다.

코드는 치팅 우려로 첨부하지 않았습니다.

팁

$\infty = 10^9$, $-\infty = 1$로 잡아도 됩니다. 쿼리 수의 최댓값과 $X$를 고려했을 때 오작동 하지 않습니다.
코드가 아주 길어지므로, C++ std::vector의 at메소드, assert 등을 적극 활용하세요.
쿼리 번호는 enum 등으로 관리하면 편합니다.
오타 조심하세요.

여러 반례를 테스트 해 보세요.
아래는 랜덤으로 데이터를 생성해주는 파이썬 코드입니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from random import randint
from pathlib import Path


with open(Path(__file__).parent / "input.txt", "w") as f:
    n = randint(1, 10000)
    f.write(f"{n}\n")
    arr = [str(randint(1, 100)) for _ in range(n)]
    f.write(f"{" ".join(arr)}\n")

    m = randint(1, 10000)
    f.write(f"{m}\n")
    for _ in range(m):
        query = randint(1, 6)
        l = randint(1, n)
        r = randint(l, n)
        f.write(f"{query} {l} {r}")
        if query <= 3:
            f.write(f" {randint(1, 10)}")
        f.write("\n")

아래는 $O(NM)$의 시간복잡도로 해결하는 파이썬 코드입니다. 데이터 생성기와 함께 반례 체크 용도로 사용하세요.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
n = int(input())
arr = list(map(int, input().split()))


def range_min(l, r, x):
    for i in range(l, r + 1):
        arr[i] = min(x, arr[i])


def range_max(l, r, x):
    for i in range(l, r + 1):
        arr[i] = max(x, arr[i])


def range_add(l, r, x):
    for i in range(l, r + 1):
        arr[i] += x


m = int(input())
for _ in range(m):
    q, *info = map(int, input().split())
    info[0] -= 1
    info[1] -= 1
    if q == 1:
        range_min(*info)
    elif q == 2:
        range_max(*info)
    elif q == 3:
        range_add(*info)
    elif q == 4:
        print(min(arr[info[0]:info[1]+1]))
    elif q == 5:
        print(max(arr[info[0]:info[1]+1]))
    elif q == 6:
        print(sum(arr[info[0]:info[1]+1]))

후기

제가 막 세그먼트 트리를 배웠을 때 풀려고 잡았던 문제인데, 구현 과정에서 실수가 자꾸 나와 결국 8달이 지나서야 풀게 됐네요.
제가 푼 문제 중 가장 어려운 문제이고, 제 자력으로 푼 다이아몬드 III 문제입니다.
저 자신이 정말 자랑스럽네요.

백준 27322번: 한별이의 퍼펙트 수열과 쿼리 교실 [C++]