526互联

P7167 [eJOI2020 Day1] Fountain 题解

发布时间 2023-09-30 15:21:48作者: Unino

Description

给定 \(n\) 个从上往下圆心重叠的圆盘，给定每个圆盘的直径 \(d_i\) 和容量 \(c_i\)，所有圆盘底下有一个容量为 \(\infty\) 的水池，编号为 \(0\)。\(q\) 次询问，每次给定 \(r\) 和 \(v\) 表示往第 \(r\) 个圆盘里倒 \(v\) 的水，输出水最后流到哪个圆盘会停止。

Solution

倍增。

第 \(i\) 个圆盘溢出所到达的下一个圆盘的编号是固定的，我们可以先预处理出每个 \(i\) 的 \(next\)，用 \(\rm ST\) 维护圆盘的直径，做 \(n-1\) 次二分分别求出 \(next_{1 \dots n-1}\)，最后让 \(next_n=n+1\)，表示流到水池。

接下来我们需要回答 \(q\) 次询问。如果按题意模拟，时间复杂度是 \(O(nq)\)，无法通过本题，但可以发现，\(i \to next_i \to next_{next_i} \to \dots\) 构成了树，于是我们记录 \(f[i,j]\) 表示从第 \(i\) 个圆盘水溢出 \(2^j\) 次到达的圆盘编号，\(g[i,j]\) 表示第 \(i\) 个圆盘溢出到 \(2^j\) 个圆盘需要水的容量，可得状态转移方程：\(f[i,j]=f[f[i,j-1],j-1],g[i,j]=g[i,j-1]+g[f[i,j-1],j-1]\)。与 \(\rm LCA\) 很像。

Code

#include <bits/stdc++.h>

#define int long long

using namespace std;

constexpr int MAX_N = 1E5 + 5;

int n, q, d[MAX_N], c[MAX_N], f[MAX_N][30], g[MAX_N][30];
int st[MAX_N][30], Log[MAX_N];

void pre_work() {
    for (int i = 2; i <= n; i++) {
        Log[i] = Log[i >> 1] + 1;
    }
    for (int i = 1; i <= n; i++) {
        st[i][0] = d[i];
    }
    for (int j = 1; j <= Log[n]; j++) {
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
        }
    }
}

int RMQ(int l, int r) {
    int k = Log[r - l + 1];
    return max(st[l][k], st[r - (1 << k) + 1][k]);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n >> q;
    
    for (int i = 1; i <= n; i++) {
        cin >> d[i] >> c[i];
    }
    
    pre_work();
    
    for (int i = 1; i < n; i++) {
        int l = i + 1, r = n + 1;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (RMQ(i + 1, mid) <= d[i]) l = mid + 1;
            else r = mid - 1;
        }
        f[i][0] = l;
        g[i][0] = c[l];
    }
    f[n][0] = n + 1;
    g[n][0] = 0;
    for (int j = 1; j < 30; j++) {
        for (int i = 1; i <= n; i++) {
            f[i][j] = f[f[i][j - 1]][j - 1];
            g[i][j] = g[i][j - 1] + g[f[i][j - 1]][j - 1];
        }
    }
    
    while (q--) {
        int r, v;
        cin >> r >> v;
        if (v <= c[r]) {
            cout << r << "\n";
        } else {
            v -= c[r];
            for (int i = 29; i >= 0; i--) {
                if (v > g[r][i]) {
                    v -= g[r][i];
                    r = f[r][i];
                }
            }
            r = f[r][0];
            cout << (r > n ? 0 : r) << "\n";
        }
    }
    
    return 0;
}