https://jungol.co.kr/problem/4973?cursor=MTIsMSw0
| 시간 제한 | 메모리 제한 |
| 6초 (ㅖ?) | 2048MB |
문제
도시에 $N$명의 사람들이 살고 있다. 이 중 일부는 참말쟁이이고, 나머지는 거짓말쟁이이다.
더욱 구체적으로, 참말쟁이들은 항상 옳은 말만을 하지만, 거짓말쟁이들은 옳은 말이든 거짓말이든 아무 말이나 한다.
모든 사람들에게, 참말쟁이들이 이 도시에 몇 명이 존재하는지 물었다.
그 결과, $i$번째 사람은 참말쟁이가 $A_i$명 이상 $B_i$명 이하라고 대답하였다.
당신이 할 일은 이 증언들을 바탕으로 가능한 참말쟁이의 최대 명수를 구하는 것이다.
그런데, 문제가 발생했다. 사람들의 기억력이 그리 좋지는 못하다는 것이다.
$Q$번 증언이 바뀌며, $i$번째 증언 바뀜에서는 $P_i$번 사람의 증언이 "참말쟁이가 $L_i$명 이상, $R_i$명 이하이다." 로 바뀐다.
초기 상태를 포함해서 $Q+1$번의 상황에 대해 각각 참말쟁이의 최대 명수를 구하여라.
입력
첫 줄에 $N$이 주어진다. $(1 \leq N \leq 5×10^5)$
$N$개의 줄에 걸쳐, $A_i$와 $B_i$가 순서대로 주어진다. $(0 \leq A_i \leq B_i \leq N)$
다음 줄에 $Q$가 주어진다. $(1 \leq Q \leq 5×10^5)$
$Q$개의 줄에 걸쳐, $P_i$, $L_i$, $R_i$가 순서대로 주어진다. $(1 \leq P_i \leq N,\ 0 \leq L_i \leq R_i \leq N) $
출력
$Q+1$개의 경우의 참말쟁이의 최대 명수를 공백으로 구분하여 순서대로 한 줄에 출력한다.
풀이
$N$명 중 $x$명 이상의 사람 $k$명이 참말쟁이의 범위를 $x$가 포함되도록 했다고 해봅시다. 그러면 $x$명의 참말쟁이가 존재하는 것이 가능합니다. $k$명 중 $x$명만 참말쟁이이고 나머지는 모두 거짓말쟁이라고 보면 되기 때문입니다. 이 문제에서 거짓말쟁이는 항상 틀린 말을 하는 것이 아니라 옳은 말이든 거짓말이든 할 수 있다는 게 중요합니다.
$N$명의 사람들이 말하는 $L, R$범위에 따라 $i$명이 그 범위에 몇 번 포함되었는지, 즉 $i$명이 참말을 하고 있다고 말한 사람이 몇 명인지를 확인해야 합니다. 그걸 `seg[i]`라고 하겠습니다. 그러면 우리는 `i` $\leq$ `seg[i]`를 만족하는 $i$중 가장 큰 값을 찾아야 합니다. 세그먼트 트리에서 인덱스를 유동적으로 비교하는 건 너무 어려우니 여기서 특별한 방법을 사용합니다. $i$번째 값을 담는 리프 노드 `seg[i+size]`에 `-i`를 담아두는 거예요. 그러면 `seg[i]` 값이 0 이상인 것 중 $i$가 큰 것을 찾아내면 됩니다.
정답 코드
segment tree를 비재귀 방식으로 돌아가는 class로 관리했습니다.
def solution():
n = int(input())
seg = SegTree(n+1)
declair = [(0,0)]
for _ in range(n):
l, r = map(int, input().split())
seg.update(l, r+1, 1)
declair.append((l, r))
res = [seg.query()]
q = int(input())
for _ in range(q):
p, l, r = map(int, input().split())
l0, r0 = declair[p]
seg.update(l0, r0+1, -1)
seg.update(l, r+1, 1)
res.append(seg.query())
declair[p] = (l, r)
print(*res)
solution()
