HDU 5806:NanoApe Loves Sequence Ⅱ

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


Problem Description

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 .

 

Input

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.

 

 

Output
For each test case, print a line with one integer, denoting the answer.

 

Sample Input
1
7 4 2
4 2 7 7 6 5 1

 

Sample Output
18

 

 

题意:求第k大的数不小于m的区间个数。

 

思路:我们可以把大于等于m的数看做1,其他数看做0,然后从左端点开始枚举,每一次加n-从左边开始的第k个大于1的位置。

 

AC代码:
#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;
}