「ZROI」陈太阳与序列

题目大意：给你一个长度为 $n$ 的序列，问有多少个区间 $[l,r]$ 满足 $a_l,a_{l+1},\cdots,a_r$ 这些数字最大值不超过最小值的 $k$ 倍。$n \leq 10^7$

$O(n \log n)$ 做法可以考虑 $min,max$ 前缀和是单调的，因此对于每个 $l$ 可以二分 $r$ 的位置，加上 RMQ 求区间最值即可。

满分做法，维护两个单调队列分别保存最大、最小值，尺取。

#include <cstdio>
#include <algorithm>

using std::max; using std::min;

int q1[1000000][2], head1 = 1, tail1; //max
int q2[1000000][2], head2 = 1, tail2; //min

int main() {
	int n, k, seed, ll, rr, l, r; long long ans = 0;
	scanf("%d%d%d%d%d", &n, &k, &seed, &ll, &rr);
	for (l = 1, r = 1; r <= n; ++r) {
		int now = seed % (rr - ll + 1) + ll;
		seed = (13331ll * seed + 23333) % 1000000007;
		while (head1 <= tail1 && max(now, q1[head1][1]) > 1LL * k * min(now, q2[head2][1])) {
			ans += r - l, ++l;
			if (q1[head1][0] < l) ++head1;
			if (q2[head2][0] < l) ++head2;
		}
		while (head1 <= tail1 && q1[tail1][1] <= now) --tail1;
		while (head2 <= tail2 && q2[tail2][1] >= now) --tail2;
		q1[++tail1][0] = r, q1[tail1][1] = now;
		q2[++tail2][0] = r, q2[tail2][1] = now;
	}
	for (; l <= n; ++l) ans += n - l + 1;
	printf("%lld\n", ans);
	return 0;
}

时间复杂度 $O(n)$