P7167 Fountain

原题

有n个盘子组成的塔，向第i个盘子上倒水，若溢出会落到下面第一个直径大的盘子里，直到落到底部的水池为止。现给出q次询问，$（r，v）$代表向第r个盘子里倒入体积为v的水，求水最终会停在哪个盘子

一开始用ST表保存区间内盘子直径最大值，给出 $r$ 后，递归求解 $[r，n]$ 区间内最大值k，并继续求 $[r，k]$ 区间内最大值，直到取到第 $r$ 个，回溯过程中逐步计算储水量。

但是看到严格单调递增序列就放弃了

然后卡了一段时间，突然发现好像有点眼熟 (

第一个想法

看正的比较难想，但横过来就很直观

当我们说水向下流，实际上我们在说水向右找到第一个比他大的盘子，那么就是单调栈了

数组 $f[i]$ 表示第i个盘子下边第一个比他大的盘子编号,这样形成链状的查询，可以依次访问

但数据量太大，时间复杂度还是很高

因此要用倍增，类似ST表的方法，每次跳跃跳2的幂次

数组 $f[i][j]$ 存储从第i个盘子开始，跳 $2^j$ 到达的盘子编号

数组 $summ[i][j]$ 存储从第i个盘子开始，到之上 $2^j$ 个盘子的储水量总和

查询的时候特判当前储水量，然后从大到小循环j，向上跳跃，最后输出父节点

第二个想法 （但是没写

可以看到在一个大的盘子之上有许多小盘子依次连接，最终汇聚到一个统一的大盘子，又最终汇聚到底部的水池

于是这提醒我们想到树

对于一个盘子，他下面第一个直径大于它的盘子为他的父节点，上面所有可以到达他的盘子为他的子树，根节点代表底部水池

那么从叶节点向上遍历即为流水顺序，在这过程中计算储水量

但是数据太大，所以仍然要用到倍增，使用类似倍增求LCA的方法，向上寻找

但是不是求公共祖先，实质上和第一种方法相同，只不过套上了树的形式

#include <iostream>#include <cstdio>#include <cstring>#include <stack>#define ll long longusing namespace std;const int N = 1e5 + 10;int n, q, d[N], c[N], R, V, f[N][20], summ[N][20];stack<int>s;inline void Monotonic_Stack() {   // 单调栈板子 	for(int i = 1; i <= n; i ++) {		while (!s.empty() && d[i] > d[s.top()]) {			f[s.top()][0] = i;			// 初始化右边第一个大的盘子编号 			summ[s.top()][0] = c[i];	// 初始化总和 			s.pop();		}		s.push(i);	}	while(!s.empty()) f[s.top()][0] = 0, s.pop();}inline void PrepareRMQ() {  // ST表板子 	for (int j = 1; (1 << j) <= n; j ++)		for (int i = 1; i <= n - (1 << j); i ++) {			f[i][j] = f[f[i][j - 1]][j - 1];			summ[i][j] = summ[i][j - 1] + summ[f[i][j - 1]][j - 1];		}}inline int query(int r, int val) {  // 计算 	if (c[r] >= val) return r;	val -= c[r];  // 先减掉当前盘子容量 	for (int i = 18; i >= 0; i --)		if (f[r][i] && val > summ[r][i]) {			val -= summ[r][i];  // 向上寻找 			r = f[r][i];		// 更新位置 		}	return f[r][0];				// 返回父节点 }int main() {	scanf("%d%d", &n, &q);	for (int i = 1; i <= n; i ++) scanf("%d%d", &d[i], &c[i]);	Monotonic_Stack();  // 单调栈 	PrepareRMQ();		// 准备工作 	while (q -- ) {		scanf("%d%d", &R, &V);		printf("%d\n", query(R, V));	}		return 0;}