分数: 500 点
问题陈述
给你一个正整数 N 和排列 P=(P _ 1,P _ 2,\ldots,P _ N) of (1,2,\ldots,N).
给你一个整数 K。 查找整数对的数量 (l,r) 满足以下两个条件。
- 1\le l\le r\le N
- 序列的倒数 (P _ l,P _ {l+1},\ldots,P _ r) 等于 K.
约束
- 1\le N\le5\times10 ^ 5
- 0\le K\le\dfrac{N(N-1)}2
- 1\le P _ i\le N\ (1\le i\le N)
- P _ i\ne P _ j\ (1\le i\lt j\le N)
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N K P _ 1 P _ 2 \ldots P _ N
输出
输出整数对的数量 (l,r) 满足条件。
样本输入 1
7 3 6 3 2 1 7 5 4
示例输出 1
5
例如序列的倒数 (P _ 1,P _ 2,P _ 3)=(6,3,2) is 3,所以 (l,r)=(1,3) 满足条件。
其他满足条件的对是 (l,r)=(2,4),(2,5),(4,7),(5,7),所以输出 5.
示例输入 2
4 1 1 2 3 4
示例输出 2
0
每个连续子序列的反转数 P is 0,所以没有对 (l,r) 满足条件。
因此,输出 0.
示例输入 3
25 18 14 19 24 8 12 11 6 5 3 13 22 15 17 2 9 4 7 18 10 25 23 16 1 20 21
示例输出 3
3