NanoApe, the Retired Dog, has returned back to prepare for for the National Higher Education Entrance Examination!
In math class, NanoApe picked up sequences once again. He wrote down a sequence with n n numbers and a number m m on the paper.
Now he wants to know the number of continous subsequences of the sequence in such a manner that the k k-th largest number in the subsequence is no less than m m.
Note : The length of the subsequence must be no less than k k.
Input
The first line of the input contains an integer T T, denoting the number of test cases.
In each test case, the first line of the input contains three integers n,m,k n,m,k.
The second line of the input contains n n integers A1,A2,...,An A1,A2,...,An, denoting the elements of the sequence.
1≤T≤10, 2≤n≤200000, 1≤k≤n/2, 1≤m,Ai≤109 1≤T≤10, 2≤n≤200000, 1≤k≤n/2, 1≤m,Ai≤109
Output
Sample Input
1
7 4 2
4 2 7 7 6 5 1
Sample Output
18
题意:问数列中有多少区间满足区间第k大数不小于m。
分析:尺取法求出以每个下标结尾的所有区间个数。
#include<iostream>
#include<string>
#include<algorithm>
#include<cstdlib>
#include<cstdio>
#include<set>
#include<map>
#include<vector>
#include<cstring>
#include<stack>
#include<queue>
#define INF 2147483640
#define eps 1e-9
#define N 200005
#define MOD 1000000007
typedef long long ll;
using namespace std;
int t,n,m,k,tot,a[N];
int main()
{
scanf("%d",&t);
for(int T = 1;T <= t;T++)
{
ll ans = 0;
int i,j,sum = 0,tot = 0;
scanf("%d%d%d",&n,&m,&k);
for(int i = 1;i <= n;i++) scanf("%d",&a[i]);
for(j = 1;j <= n && sum != k;j++)
{
if(a[j] >= m)
{
sum++;
i = j;
}
tot++;
}
if(sum != k)
{
cout<<0<<endl;
continue;
}
tot--,sum--;
for(;i <= n;i++)
{
tot++;
if(a[i] >= m) sum++;
while(sum >= k)
{
if(a[i - tot + 1] >= m) sum--;
tot--;
}
tot++;sum++;
ans += i - tot + 1ll;
}
cout<<ans<<endl;
}
}