Little Elephant and Inversions
题意翻译
## 题意翻译
给你一个长度为 n 的序列 A[1], A[2], …, A[n].
问你有多少组 (l, r) (1 <= l < r <= n) 满足
A[1], A[2], …, A[l], A[r], A[r+1], ..., A[n] 的逆序对个数不超过 k。
## **输入格式**
第一行两个整数 n,k (2<=n<=10^5,0<=k<=10^18)。下一行为一个长度为 n 的序列 A[1], A[2], …, A[n]。
## 输出格式
在一行中输出问题的答案。
题目描述
The Little Elephant has array $ a $ , consisting of $ n $ positive integers, indexed from 1 to $ n $ . Let's denote the number with index $ i $ as $ a_{i} $ .
The Little Elephant wants to count, how many pairs of integers $ l $ and $ r $ are there, such that $ 1<=l<r<=n $ and sequence $ b=a_{1}a_{2}...\ a_{l}a_{r}a_{r+1}...\ a_{n} $ has no more than $ k $ inversions.
An inversion in sequence $ b $ is a pair of elements of the sequence $ b $ , that change their relative order after a stable sorting of the sequence. In other words, an inversion is a pair of integers $ i $ and $ j $ , such that $ 1<=i<j<=|b| $ and $ b_{i}>b_{j} $ , where $ |b| $ is the length of sequence $ b $ , and $ b_{j} $ is its $ j $ -th element.
Help the Little Elephant and count the number of the described pairs.
输入输出格式
输入格式
The first line contains two integers $ n $ and $ k $ $ (2<=n<=10^{5},0<=k<=10^{18}) $ — the size of array $ a $ and the maximum allowed number of inversions respectively. The next line contains $ n $ positive integers, separated by single spaces, $ a_{1},a_{2},...,a_{n} $ $ (1<=a_{i}<=10^{9}) $ — elements of array $ a $ .
Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use cin, cout streams or the %I64d specifier.
输出格式
In a single line print a single number — the answer to the problem.
输入输出样例
输入样例 #1
3 1
1 3 2
输出样例 #1
3
输入样例 #2
5 2
1 3 2 1 7
输出样例 #2
6