名作之壁

由于n<=10^7，所以只能够是线性复杂度的做法，题意里涉及维护最大值，最小值，考虑使用单调队列维护最大值和最小值，而若[l,r]满足题意，显然【l,R】(R>r)也满足题意（因为新的最大值只会大于等于原最大值，新最小值小于等于原最小值），所以当[l,r]满足题意时，则会由n-r+1个区间均满足题意（即[l,R]）
ps:手写队列比STL常数小一些

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdio>
#include<cmath>
#define int long long
using namespace std;
const int mod=1e9;
int read()
{
    int s=0,bj=0;
    char ch=getchar();
    while(ch<'0'||ch>'9')bj|=(ch=='-'),ch=getchar();
    while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
    return bj?-s:s;
}
void printnum(int x)
{
    if(x>9)printnum(x/10);
    putchar(x%10^48);
}
void print(int x,char ch)
{
    if(x<0){putchar('-');x=-x;}
    printnum(x);putchar(ch);
}
int n,k;
int b,c;
int q1[10000005],q2[10000005],a[10000005];
int l1=1,r1,l2=1,r2;
int ans;
signed main()
{
    int L=1;
    n=read();k=read();
    a[0]=read();b=read();c=read();
    for(int i=1;i<=n;++i)
    {
        a[i]=(a[i-1]*b+c)%mod;
        while(r1>=l1&&a[q1[r1]]>=a[i])--r1;
        while(r2>=l2&&a[q2[r2]]<=a[i])--r2;//维护队列单调性
        q1[++r1]=q2[++r2]=i;
        while(a[q2[l2]]-a[q1[l1]]>k)//这一段区间满足题意
        {
            ans+=n-i+1;++L;//计算贡献
            if(q1[l1]<L)++l1;
            if(q2[l2]<L)++l2;//弹出队列
        }
    }
    print(ans,'\n');
    return 0;
}