Interval Inversion CountAI (CI翻译)
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 _ NOutput
Output the number of pairs of integers $(l,r)$ satisfying the conditions.
{"titleZh":"区间逆序数","bodyZh":"## 题目描述\n\n给定一个正整数 $N$ 和一个 $(1,2,\ldots,N)$ 的排列 $P=(P _ 1,P _ 2,\\ldots,P _ N)$。\n\n给定一个整数 $K$。请找出满足以下两个条件的整数对 $(l,r)$ 的数量。\n\n- $1\\le l\\le r\\le N$\n- 序列 $(P _ l,P _ {l+1},\\ldots,P _ r)$ 的逆序数等于 $K$。\n\n## 约束条件\n\n- $1\\le N\\le5\\times10 ^ 5$\n- $0\\le K\\le\\dfrac{N(N-1)}2$\n- $1\\le P _ i\\le N\\ (1\\le i\\le N)$\n- $P _ i\\ne P _ j\\ (1\\le i\\lt j\\le N)$\n- 所有输入值均为整数。\n\n## 输入格式\n\n输入从标准输入按以下格式给出：\n\n\nN K\nP _ 1 P _ 2 \\ldots P _ N\n$(l,r)$ 的数量。"}AI (CI翻译)
样例
7 3
6 3 2 1 7 5 4
5
4 1
1 2 3 4
0
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
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。