No.2374 「ASKT Subsequences」別解

想定解と違う方法で解いたので解法を書きたいと思います。

問題文

解法

まず、数列 $X$ があさかつ型の部分列であることは以下の条件をすべて満たすことと同値です。
・$X_2>X_3$
・$X_1=X_3-10$
・$X_4=X_2+1$
$2$ 番目の要素と $3$ 番目の要素を全探索します。この時、$1,4$ 番目の値は一意に定まります。
そのため、「$A_i=x\ (l\leq i\leq r)$ を満たす $i$ の個数」を高速に数え上げればいいことになり、これは累積和を前計算すれば $O(1)$ で求まります。
計算量は $O(N^2+NA_{max})$ です。

コード