Kazun の競プロ記録

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

AtCoder Beginner Contest 221 E問題 LEQ

AtCoder ABC ABC221 E問題 500 pts

問題

提出解答

問題の概要

長さ $N$ の整数列 $A=(A_1, \dots, A_N)$ の連続するとは限らない部分列のうち, 以下を全て満たすのはいくつか?

長さ $2$ 以上
部分列の初項は末項以下である.

制約

$1 \leq N \leq 3 \times 10^5$
$1 \leq A_i \leq 10^9$

解法

まず, 条件は整数の大小が重要であり, 値そのものが重要というわけではないので, 列 $A$ の各要素の大小関係が変わらない範囲で変換しても構わない. そこで, 以下では $A$ の代わりに $A$ の座標圧縮による変換した列を $\widetilde{A}$ とする.

$[\![N ]\!]$ で $N$ 以下の正の整数全体の集合とし, $\mathcal{A} \subset [\![N ]\!]^2$ を

$\mathcal{A}:=\{(l,r) \in [\![N ]\!]^2 \mid l < r, \widetilde{A}_l \leq \widetilde{A}_r \}$

とする. このとき,

$(l,r) \in \mathcal{A}$ であるとき, $l$ 項目を初項, $r$ 項目を末項とする部分列は全て条件を満たす.
$l$ 項目を初項, $r$ 項目を末項とする部分列は全て $(l,r) \in \mathcal{A}$ である.

よって, 求めるべき解答 $X$ は

$\displaystyle{X=\sum_{(l,r) \in \mathcal{A}} 2^{r-l-1} }$

である.

ここで, $\sum$ のとる範囲において, $l$ を固定して考える. つまり,

$\displaystyle{Y_l=\sum_{(l,r) \in \mathcal{A}} 2^{r-l-1} }$

とする. このとき, $X=Y_1+\dots+Y_N$ である.

$Y_l$ を求める際に, $l$ は定数であることから,

$\displaystyle{Y_l=\dfrac{1}{2^l} \sum_{(l,r) \in \mathcal{A}} 2^{r-1} }$

となり, 当然ながら, $l \lt r$ のときに, $2^r$ は $l$ の値に依らないことから, 以下のようにして全ての $Y_l$ を求める事ができる.

$B_1=B_2=\dots=B_K=0$ とする (ただし, $K=\max \widetilde{A}$ , つまり, $A$ にある整数の種類数).
の順に以下を実行する.
- $\displaystyle{Y_l=\dfrac{1}{2^l} \sum_{c=\widetilde{A}_l}^K B_c}$ である.
- $B_{\widetilde{A}_l}$ に $2^{l-1}$ を加算する.

ここで, $B_{\widetilde{A}_l}$ に $2^l$ を加算したあとの $B_k$ はそれぞれ, $l \leq r, \widetilde{A}_r=k$ を満たす $r$ 全てにおける $2^r$ の総和である.

このとき, $B$ においては1点加算及び, 区間和の取得が必要であり, 区間和の演算は群を成すことから, BIT 木で管理できる.

よって, 計算量 $O(\log N)$ で $Y_k$ を求められることと, $X=Y_1+\dots+Y_N$ であったので, 全体の計算量 $O(N \log N)$ で正解を求めることができる.