【题解】牛客小白月赛27_ACM竞赛_ACM/CSP/ICPC/CCPC/比赛经验/题解/资讯_牛客竞赛OJ_牛客网
来源：牛客网
考点：尺取法+单调队列（维护最值）。
设答案为ans，考虑使用尺取法，用右指针r遍历数组。若[l,r]区间内最大值与最小值之差大于k，则此时对答案的贡献为n-r+1。因为[l,r+1],[l,r+2],…,[l,n]区间的最大值只可能大于等于[l,r]区间的最大值，[l,r+1],[l,r+2],…,[l,n]区间的最小值只可能小于等于[l,r]区间的最小值。因此若[l,r]区间为畅销区间，则[l,r+1],[l,r+2],…,[l,n]区间肯定也都为畅销区间。所以只要[l,r]区间的最大值与最小值之差大于k，我们就令ans+= n-r+1，同时移动左指针，令l++，直到[l,r]区间的最大值与最小值之差小于等于k。
当右指针r遍历完整个数组，我们输出ans即可。至于维护[l,r]区间内的最大值和最小值，我们可以使用两个单调队列来实现。
#includeusing namespace std;int n,k;const int N = 1e7 + 10;long long a[N];long long q1[N],q2[N];int b,c;const int mod=1e9;int main(){ long long ans = 0; cin >> n >> k; cin >> a[0] >> b >> c; for(int i = 1 ; i <= n ; i++) a[i]=((long long)a[i-1]*b%mod + c)%mod; int l,r,l1,r1,l2,r2; l = r = 1; l1 = r1 = l2 = r2 = 0; for(; r <= n ;r++) { while(a[q1[r1 - 1]] >= a[r] && r1 > l1) r1--; //非空 ，r1 = l1 空队列 q1[r1++] = r; while(a[q2[r2 - 1]] <= a[r] && r2 > l2) r2--; //非空 ，r2 = l2 空队列 q2[r2++] = r; while(a[q2[l2]] - a[q1[l1]] > k) { ans += n - r + 1,l++; if(q1[l1] < l) l1++; //左端点超出当前范围 if(q2[l2] < l) l2++; } } cout << ans << endl; return 0;}