← 返回题目列表

AtCoder · abc452_f

F. 间隔反转计数

中文机器翻译题面 查看原题

分数: 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