/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 500 点
問題文
正整数 N と、(1,2,\ldots,N) の順列 P=(P _ 1,P _ 2,\ldots,P _ N) が与えられます。
整数 K が与えられます。 次の 2 つの条件を満たす整数の組 (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) の転倒数が 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 の連続する部分列の転倒数はすべて 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
Score : 500 points
Problem Statement
You are given a positive integer N and a permutation P=(P _ 1,P _ 2,\ldots,P _ N) of (1,2,\ldots,N).
You are given an integer K. Find the number of pairs of integers (l,r) satisfying the following two conditions.
- 1\le l\le r\le N
- The inversion number of the sequence (P _ l,P _ {l+1},\ldots,P _ r) equals K.
Constraints
- 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)
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N K P _ 1 P _ 2 \ldots P _ N
Output
Output the number of pairs of integers (l,r) satisfying the conditions.
Sample Input 1
7 3 6 3 2 1 7 5 4
Sample Output 1
5
For example, the inversion number of the sequence (P _ 1,P _ 2,P _ 3)=(6,3,2) is 3, so (l,r)=(1,3) satisfies the conditions.
The other pairs satisfying the conditions are (l,r)=(2,4),(2,5),(4,7),(5,7), so output 5.
Sample Input 2
4 1 1 2 3 4
Sample Output 2
0
The inversion number of every contiguous subsequence of P is 0, so there are no pairs (l,r) satisfying the conditions.
Thus, output 0.
Sample Input 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
Sample Output 3
3