P8251 丹钓战题解

Yansuan_HCl · 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;
}

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

P8251 丹钓战 题解

P8251 丹钓战题解