AT_abc248_h [ABC248Ex] Beautiful Subsequences

[problemUrl]: https://atcoder.jp/contests/abc248/tasks/abc248_h $ (1,\ldots,N) $ を並び替えて得られる長さ $ N $ の順列 $ P=(P_1,\ldots,P_N) $、及び整数 $ K $ が与えられます。 以下の条件を全て満たす整数組 $ (L,R) $ の個数を求めてください。 - $ 1\ \leq\ L\ \leq\ R\ \leq\ N $ - $ \mathrm{max}(P_L,\ldots,P_R)\ -\ \mathrm{min}(P_L,\ldots,P_R)\ \leq\ R\ -\ L\ +\ K $

N/A

N/A

### 制約 - $ 1\ \leq\ N\ \leq\ 1.4\times\ 10^5 $ - $ P $ は $ (1,\ldots,N) $ を並び替えて得られる順列 - $ 0\ \leq\ K\ \leq\ 3 $ - 入力は全て整数 ### Sample Explanation 1 条件を満たす組 $ (L,R) $ は以下の $ 9 $ 個です。 - $ (1,1) $ - $ (1,3) $ - $ (1,4) $ - $ (2,2) $ - $ (2,3) $ - $ (2,4) $ - $ (3,3) $ - $ (3,4) $ - $ (4,4) $ $ (L,R)\ =\ (1,2) $ は $ \mathrm{max}(A_1,A_2)\ -\mathrm{min}(A_1,A_2)\ =\ 4-1\ =\ 3 $ 、$ R-L+K=2-1+1\ =\ 2 $ となるので、条件を満たしません。