题解
Step1：单调栈处理
利用单调栈维护O(n)一个严格递减的下标栈，目的是未来在线性时间内求出每个点右侧比它大的最近位置，即：
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)，我们对每个i采用倍增预处理：
-
up[i][k]：从i出发沿nxt连走2^k步后到达的结点。
-
sum[i][k]：与之对应的这2^k个结点容量的总和（不包括i本身）
初始化：
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: 单次查询处理
-
若首次盘的容积够大，能装满水，就直接返回
-
否则，从大到小枚举倍增系数k，不断循环处理直至不能再跳为止，便找到答案。
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(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;
}