1
7 4 2
4 2 7 7 6 5 1

18

求总共有几个子区间满足区间内第k大数不小于m

记录大于等于m的数的位置  从左往右看 对于一段区间来说，如果i-j区间内有了k个不小于m的数  那么这个区间能组成 左边到上一个不小于k的数的长度+1 乘上 右边剩余的数的个数 个区间

/************************************************
┆  ┏┓　　　┏┓ ┆
┆┏┛┻━━━┛┻┓ ┆
┆┃　　　　　　　┃ ┆
┆┃　　　━　　　┃ ┆
┆┃　┳┛　┗┳　┃ ┆
┆┃　　　　　　　┃ ┆
┆┃　　　┻　　　┃ ┆
┆┗━┓　  　┏━┛ ┆
┆　　┃　  　┃　　┆　　　　　　
┆　　┃　  　┗━━━┓ ┆
┆　　┃　 AC代马 　　┣┓┆
┆　　┃　        　　┏┛┆
┆　　┗┓┓┏━┳┓┏┛ ┆
┆　　　┃┫┫　┃┫┫ ┆
┆　　　┗┻┛　┗┻┛ ┆
************************************************ */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
#include<iostream>
#include<queue>
#include<map>
#define ll long long
using namespace std;

int a[200010],Max[200010];

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,m,k;
        scanf("%d%d%d",&n,&m,&k);
        int num=0,len=0;
        ll ans=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            if(num<k)
            {
                if(a[i]>=m)
                {
                    Max[num++]=i;
                }
                if(num==k)
                {
                    ans+=(n-i+1)*(Max[0]);
                }
            }
            else if(a[i]>=m)
            {
                Max[num++]=i;
                len=num-k;
                ll l=Max[len]-Max[len-1];
                ll r=n-i+1;
                ans+=l*r;
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}

hdu NanoApe Loves Sequence Ⅱ

原文：http://blog.csdn.net/u013097262/article/details/52138255