Kazun の競プロ記録

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

AtCoder Beginner Contest 260 E問題 At Least One

AtCoder ABC ABC260 E問題 500 pts

問題

提出解答

問題の概要

以下を満たす $(1,2, \dots, N)$ の連続部分列の個数を $k=1,2, \dots, M$ それぞれの場合について求めよ.

任意の $i=1,2, \dots, N$ に対して, その連続部分列は $A_i$ または $B_i$ を含む.
長さが $k$

制約

$1 \leq N \leq 2 \times 10^5$
$2 \leq M \leq 2 \times 10^5$
$1 \leq A_i \lt B_i \leq N$

解法

上の条件を条件 (A) と呼ぶことにする.

連続部分列の末項で場合分けする. 末項が $T$ であるような連続部分列のうち, $(S,S+1, \dots, T)$ が条件 (A) を満たすための必要十分条件は $X_1, \dots, X_N$ を

$X_i=\begin{cases} 0 & (T \lt A_i) \\ A_i & (A_i \leq T \lt B_i) \\ B_i & (B_i \leq T) \end{cases}$

としたとき, $S \leq \min (X_1, \dots, X_N)$ である. 従って, $S':=\min (X_1, \dots, X_N)$ としたとき, 末項が $T$ である連続部分列では長さ $T-S'+1$ 以上 $T$ 以下の連続部分列は条件 (A) を満たし. 条件 (A) を満たすのはこれに限る.

従って, 各 $T$ を固定するごとに, 条件 (A) を満たす長さは区間であるから, 区間加算ができるようなアルゴリズムを利用する. そして, 区間加算を全て終えた後に結果を得るということから, 使うアルゴリズムとして Imos 法がある.

また, 各 $S'$ を求める際, 各 $X_i$ は高々2回しか変わらないことに着目すると, セグメント木を利用し, 1点更新で $X_i$ を更新していくことにより, $T=1,2, \dots, N$ における $S'$ を合計 $O(N \log N)$ で求めることができる.

以上から, セグメント木と Imos 法を利用することにより, それぞれの長さで条件 (A) を満たすような連続部分列の個数を求めることができ, 計算量 $O(N \log N)$ である.