ABC342 G - Retroactive Range Chmax

Competitive Programming C++ AtCoder Algorithms

2024-02-24

공식 에디토리얼

문제 링크
https://atcoder.jp/contests/abc342/tasks/abc342_g

원문 링크
https://atcoder.jp/contests/abc342/editorial/9373

먼저 수열이 아닌 \(1\)개의 정수에 대해 \(A \leftarrow \max\{A, x\}\)와 그것을 취소하는 과정을 생각해봅시다.

조작은 교환법칙이 성립하기에, 취소되지 않은 조작에 대한 \(x\)의 값의 중복집합을 힙(일반적으로 우선순위 큐)이나 균형 이진 탐색 트리(BBST) 등을 이용해 관리하는 것으로 빨리 처리하는 것이 가능합니다.

이를 적용해서 이 문제를 푸는 것을 생각해봅시다.

세그먼트 트리와 같이 \([i2^k, (i + 1)2^k]\)의 꼴로 나타낼 수 있는 \(O(N)\)개의 구간을 생각해봅시다.
그러면, 임의의 구간 \([l, r]\)에 대해서

\(A_i \leftarrow \max\{A_i, x\}\)를 갱신한다.
해당 연산의 취소

의 \(2\)가지 조작을 \(O(\log N)\)개의 중복집합에 대한 \(x\)의 추가 또는 삭제 연산으로써 구현할 수 있습니다.

값을 구하는 쿼리에 대해서도 \(A_i\)를 포함한 \(O(\log N)\)개의 중복집합 각각에 포함된 값의 최댓값을 취해, 그것들의 최댓값을 구하는 것으로 \(A_i\)의 값을 구할 수 있습니다.

시간복잡도는 적절한 자료구조를 사용하는 것으로 \(O((N + Q) \log N \log Q)\)가 됩니다.

제곱근 분할로도 풀린다고 한다.

힙이나 BBST를 이용한 공식 풀이 외에도 제곱근 분할을 이용해 푸는 해설이 존재했다.

이번 ABC는 뭔가 생각할게 많다보니 D 풀고 힘을 다하긴 했는데, 다른 문제 라인업들도 만만찮았던 듯.