自动搬运

查看原文

来自洛谷，原作者为

	Yansuan_HCl 再见了、所有的 camelCase

搬运于2025-08-24 22:37:19，当前版本为作者最后更新于2022-03-26 14:07:01，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

记第 $i$ 个二元组为 $P_i$。

对于一个区间 $[L, R]$ 按题意模拟，我们会先把 $P_L$ 入栈。对于下一个成功的二元组 $P_i$，它会把栈顶元素直到 $P_L$ 都弹出，再把自己压进去。以此类推，可以发现，每一个二元组要么被一个成功的二元组弹出去，要么留到末尾。

因此，可以记录每个二元组能被哪个二元组弹出去。按题意模拟即可。

struct P { int a, b; };
// ...
static pair<P, int> s[500005];
int p = 0;
for (int i = 1; i <= n; ++i) {
	while(p && (s[p].first.a == f[i].a || s[p].first.b <= f[i].b)) {
		nxt[s[p].second] = i; // 记录这个二元组被谁弹出去了
		--p;
	}
	s[++p] = {f[i], i};
}

此后，对于区间 $[L, R]$，首先成功的是 $P_L$，之后被 $nxt[P_L]$ 弹出去； $nxt[P_L]$ 再被 $nxt[nxt[P_L]]$ 弹出去……以此类推，顺着 $nxt$ 跳，一直跳到序列尾或是区间外。对于每个询问复杂度为 $O(n)$。无法通过。

可以使用倍增对跳的过程进行优化。记录 $nxt[i][j]$ 表示从 $j$ 处跳了 $2^i$ 此，则可以做到预处理 $O(n\log n)$，询问 $O(\log n)$。

#include<bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T& s) {
	char c = getchar();
	T f = 1; s = 0;
	while (c < '0' || c > '9') {
		if (c == '-') f = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9') {
		s = (s << 1) + (s << 3) + (c ^ 48);
		c = getchar();
	}
	s *= f;
}
const int N = 500005;
struct P{ int a, b; } f[N];

int n,q;
int nxt[21][N];

int main(){    
	read(n); read(q);
	for (int i = 1; i <= n; ++i) read(f[i].a);
	for (int i = 1; i <= n; ++i) read(f[i].b);

	static pair<P, int> s[500005]; int p = 0;
	for (int i = 1; i <= n; ++i) {
		while(p && (s[p].first.a == f[i].a || s[p].first.b <= f[i].b)) {
			nxt[0][s[p].second] = i;
			--p;
		}
		s[++p] = {f[i], i};
	}

    for (int i = 1; i <= 20; ++i) {
        for (int j = 1; j <= n; ++j)
            nxt[i][j] = nxt[i - 1][nxt[i - 1][j]]; // 处理倍增
    }
    
	while (q--){
		int cnt = 0;
		int l, r;
		read(l); read(r);
        for (int i = 20; i >= 0; --i) {
            if (nxt[i][l] && nxt[i][l] <= r) { // 向右跳，但不越过边界
                cnt += 1 << i; // 跳了 2^i 次
                l = nxt[i][l];
            }
        }
		printf("%d\n", cnt + 1); // 要算上 L 本身
	}
	return 0;
}

不需要任何高级数据结构。