题意理解

我们有 $N$ 个装置从上到下排列，每个装置有：

• 直径 $D_i$
• 容量 $C_i$

规则：

• 向某个装置注入超过容量的水时，多余的水会向下流到最近的一个直径严格大于当前装置的装置。
• 如果下方没有直径更大的装置，水就流向水路（输出 $0$）。
• 每个询问 $(R_i, V_i)$ 互相独立：从装置 $R_i$ 注入 $V_i$ 升水，问最后停在哪个装置（或水路）。

---

核心思路

1. 建立水流后继关系

对于每个装置 $i$，我们需要知道它溢出的水流向哪里。

关键观察：
水会流向在 $i$ 之后第一个直径大于 $D_i$ 的装置。
这可以用 单调栈 在 $O(N)$ 时间内求出：

• 从下到上遍历装置（$i = N$ 到 $1$）
• 维护一个栈，栈内直径递增（栈顶最小）
• 对于装置 $i$，弹出栈顶所有直径 $\le D_i$ 的装置，那么栈顶就是第一个直径 $> D_i$ 的装置（即后继）
• 将 $i$ 压入栈

这样我们得到数组 nxt[i] 表示装置 $i$ 溢出的水流向的装置编号（如果没有，nxt[i] = 0 表示流向水路）。

---

2. 问题转化

从 $R_i$ 开始注入 $V_i$ 水：

• 如果 $V_i \le C_{R_i}$，水全部停在 $R_i$，答案就是 $R_i$。
• 否则，多余的水 $V_i - C_{R_i}$ 流向 nxt[R_i]，并继续这个过程。

这形成了一条链：$R_i \to nxt[R_i] \to nxt[nxt[R_i]] \to \dots \to 0$

我们需要沿着这条链走，直到找到第一个装置 $j$，使得从 $R_i$ 流到 $j$ 的累计多余水量 $\le C_j$。

---

3. 暴力不可行

直接模拟链可能很长，最坏 $O(N)$ per query，总复杂度 $O(NQ)$ 会超时。

---

4. 倍增优化

我们预处理：

• up[j][i]：从装置 $i$ 开始，溢出 $2^j$ 次后到达的装置编号
• sum[j][i]：从装置 $i$ 开始，溢出 $2^j$ 次所经过的累计容量（不包括终点容量）

初始化：

• up[0][i] = nxt[i]
• sum[0][i] = C[i]（因为第一次溢出需要先填满 $i$ 的容量）

转移：

up[j][i] = up[j-1][ up[j-1][i] ]
sum[j][i] = sum[j-1][i] + sum[j-1][ up[j-1][i] ]

注意边界：如果 up[j-1][i] = 0，则 up[j][i] = 0, sum[j][i] = sum[j-1][i]。

---

5. 查询过程

对于查询 $(R, V)$：

1. 如果 $V \le C_R$，直接输出 $R$。
2. 否则，令 $curr = R$，$rem = V - C_R$（当前剩余要流出的水量）。
3. 从 $j = \lceil \log N \rceil$ 到 $0$：
   • 如果 up[j][curr] != 0 且 rem > sum[j][curr]：
     • rem -= sum[j][curr]
     • curr = up[j][curr]
4. 此时再走一步就会停：
   • 如果 nxt[curr] = 0，输出 $0$（流向水路）
   • 否则，如果 rem <= C[nxt[curr]]，输出 nxt[curr]
   • 否则，理论上不会发生，因为 rem 已经小于等于下一步所需溢出的总容量

实际上更简单的写法：
我们直接倍增找到最后一个使得累计容量 $< rem$ 的点，然后它的下一个点就是答案。

---

6. 算法步骤

1. 读入数据。
2. 单调栈求 nxt[]。
3. 预处理倍增数组 up[][] 和 sum[][]。
4. 对每个查询：
   • 如果 $V \le C_R$，输出 $R$。
   • 否则：
     • $rem = V - C_R$
     • $curr = R$
     • 从高位到低位尝试跳 $2^j$ 步：
       • 如果 up[j][curr] != 0 且 sum[j][curr] < rem：
         • $rem -= sum[j][curr]$
         • $curr = up[j][curr]$
     • 如果 nxt[curr] = 0，输出 $0$
     • 否则输出 nxt[curr]

---

复杂度分析

• 单调栈：$O(N)$
• 倍增预处理：$O(N \log N)$
• 每个查询：$O(\log N)$
• 总复杂度：$O((N+Q) \log N)$，可过 $10^5$ 规模。

---

总结

这道题的关键在于：

1. 用单调栈建立溢出关系
2. 将问题转化为链上的跳跃查询
3. 使用倍增法快速定位最终位置

这种“单调栈建树/链 + 树上倍增”是处理此类问题的经典模式。