名作之壁-题解

题目描述
《无限的斯特拉托斯》又称之为名作之壁，其销量一直被圈内人士津津乐道。给你n个数字，第i个数字a[i]表示名作之壁第ii天的销量。若某段区间[l,r][l,r]中最大值和最小值之差大于kk，则称该区间为畅销区间。请问一共有多少个区间为畅销区间？
思路：两个单调队列，记录最大值最小值，然后比较记录答案。
代码：

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int n,k,cnt1=0,cnt2=0,f1=0,f2=0;
long long a[10000007],q1[10000007],q2[10000007],b,c;
const int mod=1e9;
int main()
{
    scanf("%d%d",&n,&k);
    scanf("%lld%lld%lld",&a[0],&b,&c);
    int l=1,i;
    //q1[cnt1++]=a[0];//da
    //q2[cnt2++]=a[0];//xiao
    long long ans=0;
    for(i=1;i<=n;i++){
        a[i]=(a[i-1]*b+c)%mod;
        //printf("%lld\n",a[i]);
        while(cnt1>f1&&q1[cnt1-1]<a[i])cnt1--;
        q1[cnt1++]=a[i];
        while(cnt2>f2&&q2[cnt2-1]>a[i])cnt2--;
        q2[cnt2++]=a[i];
        //printf("%d %d %lld %lld\n",f1,f2,q1[f1],q2[f2]);
        while(q1[f1]-q2[f2]>k&&f1<cnt1&&f2<cnt2){
            ans+=n-i+1;
            if(q1[f1]==a[l])f1++;
            if(q2[f2]==a[l])f2++;
            l++;
        }
        //printf("%d\n",ans);
    }
    printf("%lld\n",ans);
    return 0;
}