[P8251 NOI Online 2022 提高组] 丹钓战 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
容易发现对于一次查询 \([L, R]\)，\(L\) 一定是第一个入栈的，也是成功的，答案至少为 \(1\)；
那么下一个成功的二元组是多少呢？
每一个二元组入栈时有可能会把栈里某个二元组弹出去；
目前栈底是 \(L\)，那下一个成功的就应该是把 \(L\) 弹出去然后自己进栈的那个二元组了，然后显然这个二元组之前都在 \(L\) 的上面所以都不成功；
也就是说下一个二元组应该是从 \(L\) 往后依次进栈，把 \(L\) 弹出的那个二元组，我们记作 \(nxt[L]\)；
那么再下一个成功的二元组是多少呢？就是弹出 \(nxt[L]\) 的二元组，也就是 \(nxt[nxt[L]]\)；
可以很轻松证明一次查询里，有且只有 \(L, nxt[L], nxt[nxt[L]], nxt[nxt[nxt[L]]], \cdots\)（不超过 \(R\)）是成功的；
考虑求解 \(nxt\) 数组，按题意从第一个二元组模拟到第 \(n\) 个求解就行了，复杂度 \(\mathcal{O}(n)\)；
但是单次回答询问 \(\mathcal{O}(n)\) 无法承受；
很容易想到 \(L, nxt[L], nxt[nxt[L]], nxt[nxt[nxt[L]]], \cdots\) 可以非常裸地套用倍增优化；
\(nxt[i][j]\) 表示第 \(i\) 个二元组往后跳第 \(2^j\) 个成功二元组是多少，这个 \(\mathcal{O}(n\log n)\) 预处理好；
然后回答 \(\mathcal{O}(\log n)\) 跳就可以了。这题就做完了。
想一想，大概本题思维重点是对于任何一个区间 \([L, R]\) 上考虑，由于入栈顺序的确定性，\(nxt[i]\) 的定义、值也是确定的。所以求解 \(nxt\) 数组直接整体跑一遍然后应用在每一个区间上，达到加速目的。
/*
* @Author: crab-in-the-northeast
* @Date: 2022-09-27 09:21:24
* @Last Modified by: crab-in-the-northeast
* @Last Modified time: 2022-09-27 09:45:09
*/
#include <bits/stdc++.h>
inline int read() {
int x = 0;
bool flag = true;
char ch = getchar();
while (!isdigit(ch)) {
if (ch == '-')
flag = false;
ch = getchar();
}
while (isdigit(ch)) {
x = (x << 1) + (x << 3) + ch - '0';
ch = getchar();
}
if(flag)
return x;
return ~(x - 1);
}
const int maxn = (int)5e5 + 5;
const int lgn = 20;
int a[maxn], b[maxn], nxt[maxn][lgn];
int main() {
int n = read(), q = read();
for (int i = 1; i <= n; ++i)
a[i] = read();
for (int i = 1; i <= n; ++i)
b[i] = read();
std :: stack <int> s;
for (int i = 1; i <= n; ++i) {
while (!s.empty()) {
int x = s.top();
if (a[i] == a[x] || b[i] >= b[x]) {
nxt[x][0] = i;
s.pop();
} else
break;
}
s.push(i);
}
while (!s.empty()) {
int x = s.top();
nxt[x][0] = n + 1;
s.pop();
}
nxt[n + 1][0] = n + 1;
for (int d = 1; d < lgn; ++d)
for (int i = 1; i <= n + 1; ++i)
nxt[i][d] = nxt[nxt[i][d - 1]][d - 1];
while (q--) {
int l = read(), r = read();
int ans = 1;
for (int d = lgn - 1; d >= 0; --d) {
if (nxt[l][d] <= r) {
ans += 1 << d;
l = nxt[l][d];
}
}
printf("%d\n", ans);
}
return 0;
}