51nod 1495 中国好区间【2-pointers】

Description

阿尔法在玩一个游戏，阿尔法给出了一个长度为n的序列，他认为，一段好的区间，它的长度是>=k的，且该区间的第k大的那个数，一定大于等于T。那么问题来了，阿尔法想知道有多少好的区间。

由于阿尔法的序列长度实在是太大了，无法在规定时间内读入。

他想了一个绝妙的方法。

读入a[0],b,c,p，则a[i]=(a[i-1]*b+c)mod p。

样例解释：

a1~a5分别为47,135,247,35,147

对应的7个区间分别为[1,3],[2,3],[1,4],[2,4],[1,5],[2,5],[3,5]

对于重复的数字1，2，2 第一大是2，第二大也是2，第三大是1。

题解

只要一个区间中大于等于K的数大于等于T个，这个区间就是好区间，那么，只要枚举左端点，右端点往右推，每次累计答案n−r+1。

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 10000006
#define LL long long
using namespace std;
int k,T,n,b,c,p;
LL ans,a[maxn];
int main(){
    freopen("china.in","r",stdin);
    freopen("china.out","w",stdout);
    scanf("%d%d%d%d%d%d%d",&n,&k,&T,&a[0],&b,&c,&p);
    for(int i=1;i<=n;i++)a[i]=(a[i-1]*b+c)%p;
    int num=a[1]>=T,r=1;
    for(int i=1;i<=n;i++){
        while(r<n&&num<k)num+=a[++r]>=T;
        if(num>=k)ans+=n-r+1;
        num-=a[i]>=T;
    }
    printf("%lld\n",ans);
    return 0;
}