NanoApe Loves Sequence Ⅱ
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 262144/131072 K (Java/Others)
Total Submission(s): 520 Accepted Submission(s): 253
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 numbers and a number on the paper.
Now he wants to know the number of continous subsequences of the sequence in such a manner that the -th largest number in the subsequence is no less than .
Note : The length of the subsequence must be no less than .
The first line of the input contains an integer , denoting the number of test cases.In each test case, the first line of the input contains three integers .
The second line of the input contains integers , denoting the elements of the sequence.
1
7 4 2
4 2 7 7 6 5 1
18
题意：求第k大的数不小于m的区间个数。
思路：我们可以把大于等于m的数看做1,其他数看做0，然后从左端点开始枚举，每一次加n-从左边开始的第k个大于1的位置。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
__int64 a[200005];
int main()
{
__int64 T;
scanf("%I64d",&T);
while(T--)
{
__int64 n,m,k,t;
scanf("%I64d%I64d%I64d",&n,&m,&k);
for(int i=0; i<n; i++)
{
scanf("%I64d",&t);
a[i]=(t>=m)?1:0;
}
__int64 l=0,r=0,sum=a[0],ans=0;
while(r<n)
{
if(sum==k)
{
ans+=n-r;
sum-=a[l++];
}
else sum+=a[++r];
}
printf("%I64d\n",ans);
}
return 0;
}
