题解

Step1：单调栈处理

利用单调栈维护O(n)O(n)一个严格递减的下标栈，目的是未来在线性时间内求出每个点右侧比它大的最近位置，即：

nxt[i]=min⁡{j>i ∣ Dj>Di} (若不存在, nxt[i]=0)nxt[i] = \min \{ j > i \space | \space D_j > D_i \}\space (若不存在, \space nxt[i]=0)
void init_nxt() {
    for (int i = n; i >= 1; i --) {
        while(!st.empty() && d[st.top()] <= d[i]) {
            st.pop();
        }
        up[i][0] = st.empty() ? 0 : st.top();
        sum[i][0] = up[i][0] ? 1ll * c[up[i][0]] : 0ll;
        st.push(i);
    }
}

Step2：链上倍增跳

为了把单次查询做到O(logN)O(logN)，我们对每个ii采用倍增预处理：

  • up[i][k]up[i][k]：从ii出发沿nxtnxt连走2k2^k步后到达的结点。

  • sum[i][k]sum[i][k]：与之对应的这2k2^k个结点容量的总和（不包括ii本身）

初始化：

up[i][0]=nxt[i]sum[i][0]=C[nxt[i]](nxt[i]≠0)sum[i][0]=0(nxt[i]=0)递推：先走半段，再接半段mid=up[i][k−1]up[i][k]=up[mid][k−1](mid≠0)up[i][k]=0(mid=0)sum[i][k]=sum[i][k−1]+sum[mid][k−1](mid≠0)sum[i][k]=sum[i][k−1](mid=0)up[i][0] = \mathrm{nxt}[i] \\[4pt] sum[i][0] = C[{\mathrm{nxt}[i]]} \quad (\mathrm{nxt}[i]\neq 0) \\ sum[i][0] = 0 \quad (\mathrm{nxt}[i]=0) \\[8pt] \text{递推：先走半段，再接半段} \\[4pt] mid = up[i][k-1] \\[4pt] up[i][k] = up[mid][k-1] \quad (mid \neq 0) \\ up[i][k] = 0 \quad (mid = 0) \\[4pt] sum[i][k] = sum[i][k-1] + sum[mid][k-1] \quad (mid \neq 0) \\ sum[i][k] = sum[i][k-1] \quad (mid = 0)
void init_lift() {
    for (int k = 1; k < LOGN; k ++) {
        for (int i = 1; i <= n; i ++) {
            int mid = up[i][k - 1]; // 先跳2^(k-1)步
            if (mid) {
                up[i][k] = up[mid][k - 1];
                sum[i][k] = sum[i][k - 1] + sum[mid][k - 1];
            } else {
                up[i][k] = 0;
                sum[i][k] = sum[i][k - 1]; 
            }
        }
    }
}

Step3: 单次查询处理

  1. 若首次盘的容积够大，能装满水，就直接返回

  2. 否则，从大到小枚举倍增系数kk，不断循环处理直至不能再跳为止，便找到答案。

ll query(int r, int v) {
    if (c[r] >= v) {
        return r;
    }
    v -= c[r];
    for (int k = LOGN - 1; k >= 0; k --) {
        if (up[r][k] && sum[r][k] < v) {
            v -= sum[r][k];
            r = up[r][k];
        }
    }
    return up[r][0];
}

完整代码

时间复杂度：O((N+Q)logN)O((N+Q)logN)

空间复杂度：O(NlogN)O(NlogN)

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e5 + 10;

const int LOGN = 20;

int n, q;
int d[N], c[N];
int up[N][LOGN];// up[i][k]：从 i 出发沿 nxt 走 2^k 步到达的节点
ll sum[N][LOGN];// sumv[i][k]：对应这 2^k 段的容量总和（不含 i 自身）

stack<int> st;

void init_nxt() {
    for (int i = n; i >= 1; i --) {
        while(!st.empty() && d[st.top()] <= d[i]) {
            st.pop();
        }
        up[i][0] = st.empty() ? 0 : st.top();
        sum[i][0] = up[i][0] ? 1ll * c[up[i][0]] : 0ll;
        st.push(i);
    }
}

void init_lift() {
    for (int k = 1; k < LOGN; k ++) {
        for (int i = 1; i <= n; i ++) {
            int mid = up[i][k - 1]; // 先跳2^(k-1)步
            if (mid) {
                up[i][k] = up[mid][k - 1];
                sum[i][k] = sum[i][k - 1] + sum[mid][k - 1];
            } else {
                up[i][k] = 0;
                sum[i][k] = sum[i][k - 1]; 
            }
        }
    }
}

ll query(int r, int v) {
    if (c[r] >= v) {
        return r;
    }
    v -= c[r];
    for (int k = LOGN - 1; k >= 0; k --) {
        if (up[r][k] && sum[r][k] < v) {
            v -= sum[r][k];
            r = up[r][k];
        }
    }
    return up[r][0];
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; i ++) {
        cin >> d[i] >> c[i];
    }
    init_nxt();
    init_lift();
    while(q --) {
        int r, v;
        cin >> r >> v;
        cout << query(r, v) << endl;
    }
    return 0;
}