51nod1495 中国好区间

双指针扫一遍

#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
using namespace std;
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define dwn(i,s,t) for(int i=s;i>=t;i--)
#define clr(x,c) memset(x,c,sizeof(x))
#define ll long long
int read(){
	int x=0;char c=getchar();
	while(!isdigit(c)) c=getchar();
	while(isdigit(c)) x=x*10+c-'0',c=getchar();
	return x;
}
char sh[15];
void print(int x){
	int cnt=0;
	while(x) sh[++cnt]=x%10,x/=10;
	dwn(i,cnt,1) putchar(sh[i]+48);
	putchar(32);
}
const int nmax=1e7+5;
bool a[nmax];
int main(){
	int n=read(),k=read(),T=read(),a0=read(),b=read(),c=read(),p=read();
	rep(i,1,n) if((a0=((ll)a0*b+c)%p)>=T) a[i]=1;
	int l=0,r=0,cnt=0;ll ans=0;
	while(1){
		if(a[l]) --cnt;++l;
		while(cnt<k&&r<=n) cnt+=a[r++];
		if(cnt==k) ans+=n-r+2;
		else break;
	}
	printf("%lld
",ans);
	return 0;
}

1495 中国好区间

基准时间限制：0.7 秒空间限制：131072 KB 分值: 80 难度：5级算法题

关注

阿尔法在玩一个游戏，阿尔法给出了一个长度为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。

Input

读入一行，7个数字，表示n(n<=10000000),k(k<=n),T,a[0],b,c,p。
所有数字均为正整数且小于等于10^9。

Output

输出一行表示好区间的个数。

Input示例

5 2 100 10 124 7 300

Output示例