Kazun の競プロ記録

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

AtCoder Beginner Contest 247 E問題 Max Min

AtCoder ABC ABC247 E問題 500 pts

問題

提出解答

問題の概要

整数の列 $A=\left(A_i \right)_{i=1}^N$ が与えられる. 次を満たす整数の組 $(L,R)$ の数を求めよ.

$1 \leq L \leq R \leq N$
$A_L, A_{L+1}, \dots, A_R$ の最大値が $X$ , 最小値が $Y$

制約

$1 \leq N \leq 2 \times 10^5$
$1 \leq A_i \leq 2 \times 10^5$
$1 \leq Y \leq X \leq 2 \times 10^5$

解法

$1 \leq L \leq R \leq N$ を満たす非負整数の組 $(L,R)$ と, $A$ の空ではない連続する部分列は一対一に対応する *1.

ここで, 整数 $a_1, \dots, a_k$ と整数 $x$ に対して,

$\max(a_1, \dots, a_k)=x \iff (a_1, \dots, a_k \leq x)$ かつ ( $a_1, \dots, a_k \leq x-1$ ではない).

である. $x,y$ に対して, $f(A;y,x)$ で $A$ の空ではない部分列のうち, 各項が $Y$ 以上 $X$ 以下であるものの個数とする.

$\min(A_L, \dots, A_R)=Y, \max(A_L, \dots, A_R)=X$ であることの条件は上での記述を参考にし, 包除原理を利用することにより, 求めるべき答えは

$f(A;Y,X)-f(A;Y+1,X)-f(A;Y,X-1)+f(A;Y+1,X-1)$

となる.

最後に $f(A;y,x)$ を求める方法を考える. $y \leq A_i \leq x$ を満たさないような $i$ を $1 \leq i_1 \lt i_2 \lt \dots \lt i_r \leq N$ とする. このとき,

$\displaystyle f(A;y,x)=\sum_{j=1}^{r+1} \dfrac{(i_j-i_{j-1}-1)(i_j-i_{j-1})}{2}$

である. ただし, $i_0=0, i_{r+1}=N+1$ とする.

これにより, 時間計算量 $O(N)$ で求めることができた.

*1:対応の方法: $(L,R)$ に対して, $A$ の第 $L$ 項から第 $R$ 項までの部分列を対応させる.