分析

考虑答案的单调性，我们先钦定一个值为最小值或最大值。那么如果 是一个满足的区间，那么 也一定是一个合法区间。对于每一个数都求出它的分界点。那么 。这个直接上单调队列。时间复杂度为 。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e7 + 100,P = 1e9;
int n,a[N],k,b,c;
int q[N],ans[N],l,r,len;
int main()
{
    cin >> n >> k >> a[0] >> b >> c;
    for(int i = 1;i <= n;i++) a[i] = (1LL * a[i-1] * b + c) % P;
    l = 1;r = 0;len = 0;
    for(int i = 1;i <= n;i++) {
        while(l <= r && a[q[l]] > a[i] + k) len = q[l],l++;
        ans[i] = max(ans[i],len);
        while(l <= r && a[q[r]] <= a[i]) r--;
        q[++r] = i;
    }
    l = 1;r = 0;len = 0;
    for(int i = 1;i <= n;i++) {
        while(l <= r && a[q[l]] < a[i] - k) len = q[l],l++;
        ans[i] = max(ans[i],len);
        while(l <= r && a[q[r]] >= a[i]) r--;
        q[++r] = i;
    }
    long long Ans = 0;
    for(int i = 1;i <= n;i++) Ans += ans[i];
    cout << Ans << endl;
    return 0;
}