【HDU】5806 - NanoApe Loves Sequence Ⅱ（尺取法）

退役狗 NanoApe 滚回去学文化课啦！

在数学课上，NanoApe 心痒痒又玩起了数列。他在纸上随便写了一个长度为 nn 的数列，他又根据心情写下了一个数 mm。

他想知道这个数列中有多少个区间里的第 kk 大的数不小于 mm，当然首先这个区间必须至少要有 kk 个数啦。

第一行为一个正整数 TT，表示数据组数。

每组数据的第一行为三个整数 n,m,kn,m,k。

第二行为 nn 个整数 A_iA​i​​，表示这个数列。

1 \le T \le 10,~2 \le n \le 200000,~1 \le k \le n/2,~1 \le m,A_i \le 10^91≤T≤10, 2≤n≤200000, 1≤k≤n/2, 1≤m,A​i​​≤10​9​​

对于每组数据输出一行一个数表示答案。

1
7 4 2
4 2 7 7 6 5 1

18

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define INF 0x3f3f3f3f
#define CLR(a,b) memset(a,b,sizeof(a))
int main()
{
    int n,m,k;
    int u;
    int num[200011];
    __int64 ans;
    scanf ("%d",&u);
    while (u--)
    {
        scanf ("%d %d %d",&n,&k,&m);
        for (int i = 1; i <= n ; i++)
            scanf ("%d",&num[i]);
        int s = 0;
        int st = 1;
        ans = 0;
        for (int i = 1; i <= n ; i++)
        {
            if (num[i] >= k)
                s++;
            if (s == m)
            {
                while (num[st] < k)
                {
                    st++;
                    ans += (n-i+1);
                }
                ans += (n-i+1);
                s--;
                st++;
            }
        }
        printf ("%I64d\n",ans);
    }
    return 0;
}