Kazun の競プロ記録

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

AtCoder Beginner Contest 256 D問題 Union of Interval

AtCoder ABC ABC256 D問題 400 pts

問題

提出解答

問題の概要

実数 $a,b$ に対して, $[a,b):=\{x \in \mathbb{R} \mid a \leq x \lt b\}$ とする.

$\displaystyle S:=\bigcup_{i=1}^N [L_i, R_i)$ としたとき, 次を満たすような右半開区間の列 $([X_1, Y_1), \dots, [X_K, Y_K))$ のうち, $K$ が最小であるような列の一例を求めよ.

$\displaystyle \bigcup_{k=1}^K [X_k, Y_k)=S$

制約

$2 \leq N \leq 2 \times 10^5$
$1 \leq L_i \lt R_i \leq 2 \times 10^5$

解法

$\chi_S$ で $S$ に関する定義関数とする. つまり, 整数 $x \in \mathbb{Z}$ に対して,

$\chi_S(x):=\begin{cases} 1 & (x \in S) \\ 0 & (x \not \in S) \end{cases}$

となる.

このとき, 整数 $x$ に対して,

$\displaystyle x \in S \iff \chi_S(x)=1 \iff \sum_{j=1}^N [L_j \leq x \lt R_j ] \geq 1$

である. なお,

$[L_j \leq x \lt R_j ]=\begin{cases} 1 & (L_j \leq x \lt R) \\ 0 & ({\rm otherwise}) \end{cases}$

である.

ここで, $\displaystyle \sum_{j=1}^N [L_j \leq x \lt R_j]$ について, 最初に与えられた情報だけで求められ, それ以降この値は全ての $x$ について変化することはない. この場合, Imos 法を用いることによって, $1$ 以上 $M$ 以下の範囲を一気に $O(N+M)$ で求める事ができる.

そして, $\sum_{j=1}^N [L_j \leq x \lt R_j ]$ が $1$ 以上であるような極大の (整数の) 区間達をそれぞれ

$[x_1, y_1), \dots, [x_l, y_l)$

としたとき, 実はこれがそのまま条件を満たす.