题面

有 $n$ 个容器，从最高层到最底层分别编号为 $1,2,\cdots,n$ 。

现在会在这些容器中倒上一些香槟，当第 $i$ 层容器倒满时，多余的香槟会流到第 $i+1$ 层中，如果第 $n$ 层容器也满了香槟就会流到外面去。第 $i$ 层容器的容量为 $a_i$ ，不保证 $a$ 递增。

你需要实现下面两种操作 $q$ 次：

1. 往某一个编号为 $x$ 的容器中倒入 $v$ 体积的香槟。
2. 求出某一个编号为 $k$ 的容器中的香槟体积。

$n,q\leq10^5$ 。

题解

第一个想法是吉司机线段树，大概是数据结构学傻了。吉司机做法大概是，用线段树维护还剩下的空间，支持操作：区间和、区间赋 0、单点加（实际上是减），流程是二分找到水流到哪里（其中用到区间和 check），然后区间赋 0，单点改。复杂度 $\mathcal{O}(q\log^2n)$ 。

这么做性质是冗余的。实际上可以并查集做，一段连续的 0 的下标放在同一个集合里。复杂度均摊 $\mathcal{O}(q+\alpha(n))$ 。

代码

const int N = 1e5 + 5;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	int n;
	int a[N], b[N];
	int fa[N];
	int find (int k) { return fa[k] == k? k: fa[k] = find(fa[k]); }
	int main () {
		n = Read();
		for (int i = 1; i <= n; i++) b[i] = a[i] = Read(), fa[i] = i;
		for (int q = Read(); q--; ) {
			int opt = Read(), x = Read();
			if (opt == 1) {
				int val = Read();
				if (fa[x] != x) x = find(x);
				else {
					if (b[x] > val) b[x] -= val, val = 0;
					else val -= b[x], b[x] = 0;
				}
				for (int y = x + 1, lst = x; y <= n && val; lst = y, y++) {
					if (fa[y] != y) y = find(y);
					if (b[y] > val) b[y] -= val, val = 0;
					else val -= b[y], b[y] = 0, fa[lst] = y;
				}
			} else {
				if (!b[x] || fa[x] != x) printf ("%d\n", a[x]);
				else printf ("%d\n", a[x] - b[x]);
			}
		}
		return 0;
	}
}

int main () {
	freopen("vessels.in", "r", stdin);
	freopen("vessels.out", "w", stdout);
	Main::main();
	return 0;
}