Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 237 G 問題 Range Sort Query

AtCoder ABC ABC237 G問題 600 pts

問題

提出解答

問題の概要

$(1,2, \dots, N)$ の並び替え $P$ が与えられる. 次の $Q$ 個のクエリを順に処理した場合, $X$ はどこにあるか?

$C_i=1$ のとき, $P_L, P_{L+1}, \dots, P_R$ を昇順に並び替える.
$C_i=2$ のとき, $P_L, P_{L+1}, \dots, P_R$ を降順に並び替える.

制約

$1 \leq N \leq 2 \times 10^5$
$1 \leq Q \leq 2 \times 10^5$
$1 \leq X \leq N$
$P$ は $(1,2, \dots, N)$ の並び替え
$C_i \in \{1,2\}$
$1 \leq L_i \leq R_i \leq N$

解法

求めるのは最終的な $X$ の位置である. それ以外の値については完全にわかる必要がない. そこで, 次のように $A$ を作成する.

$P_i \lt X$ ならば, $A_i=(1,0,0)$
$P_i=X$ ならば, $A_i=(0,1,0)$
$P_i \gt X$ ならば, $A_i=(0,0,1)$

このとき, $A$ における $(0,1,0)$ の場所を求めることになる.

$C_i=1$ の場合の処理を考える. $A_{L_i}+\dots+A_{R_i}=(p,q,r)$ であったとすると, $A_{L_i}, \dots, A_{R_i}$ に $(1,0,0), (0,1,0), (0,0,1)$ がそれぞれ $p,q,r$ 個あることになる. $P$ について昇順に並び替えることを念頭に入れると, $A_{L_i}, \dots, A_{R_i}$ をそれぞれ $(1,0,0)$ を $p$ 個, $(0,1,0)$ を $q$ 個, $(0,0,1)$ を $r$ 個この順に並べたものに変更すれば良い. $C_i=2$ の場合も同様である.

上の処理において, 区間和と区間更新を得意とするデータ構造が必要になる. これは例えば遅延評価セグメント木が該当する. 遅延評価セグメントを用いた場合, $O(N+Q \log N)$ で処理を完了することができる.