AT_abc248_h [ABC248Ex] Beautiful Subsequences
题目描述
给定一个由 $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$ $K$ $P_1$ $P_2$ $\ldots$ $P_N$
输出格式
请输出答案。
说明/提示
## 限制条件
- $1 \leq N \leq 1.4 \times 10^5$
- $P$ 是 $1,\ldots,N$ 的一个排列
- $0 \leq K \leq 3$
- 输入均为整数
## 样例解释 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$，因此不满足条件。
由 ChatGPT 4.1 翻译