C++(clang++11) 解法, 执行用时: 289ms, 内存消耗: 157048K, 提交时间: 2021-01-18 11:19:14

#include<bits/stdc++.h>
using namespace std;
const int N=1e7+10;
const int mod=1e9 ;
#define int long long
int q1[N],q2[N],a[N],hh,tt=-1,hh1,tt1=-1;
signed main()
{
	int n,k;
	int a0,b,c,L=1;
	cin>>n>>k>>a[0]>>b>>c;
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		a[i]=(a[i-1]*b+c)%mod;
		while(hh<=tt && a[i]>=a[q1[tt]])	--tt;//单调递减队列
		while(hh1<=tt1 && a[i]<=a[q2[tt1]])	--tt1;//单调递增队列
		q1[++tt]=i,q2[++tt1]=i;
		while(a[q1[hh]]-a[q2[hh1]]>k)
		{
			ans+=n-i+1; L++;
			if(q1[hh]<L)	hh++;
			if(q2[hh1]<L)	hh1++;
		}

	}
	cout<< ans << endl;
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 266ms, 内存消耗: 78656K, 提交时间: 2020-09-10 09:46:11

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int nx=1e7+5;
const ll mod=1e9;
int n,k,a[nx],mi[nx],mx[nx],b,c;
int main(){
	cin>>n>>k>>a[0]>>b>>c;
	int f=1,r=0,nf=1,nr=0;
	ll ans=0;
	for(int i=1,l=1;i<=n;++i){
		a[i]=(1ll*a[i-1]*b+c)%mod;
		while(f<=r&&a[i]>=a[mx[r]])--r;
		mx[++r]=i;
		while(nf<=nr&&a[i]<=a[mi[nr]])--nr;
		mi[++nr]=i;
		while(a[mx[f]]-a[mi[nf]]>k){
			ans+=n-i+1,++l;
			if(mx[f]<l)++f;
			if(mi[nf]<l)++nf;
		}
	}
	cout<<ans;
}