题意：从上到下有n个杯子，编号从1到n。每个杯子有一定体积v[i]. 两种操作：1 x y, 向x水杯倒y水; 2 x， 询问x水杯有多少水. (水杯水溢出会往下流)
n,q <= 2e5
思路：暴力倒水的话是n*q，很多次要经过满的水杯，很费时，可以用并查集维护每个水杯往下的第一个非满的水杯。
代码：
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn = 1e6+5; int a[maxn], cur[maxn], pre[maxn]; int Find(int x) { int r = x; while(pre[r] != r) r = pre[r]; int i = x, j; while(pre[i] != r) { j = pre[i]; pre[i] = r; i = j; } return r; } void join(int x, int y) { int a = Find(x); int b = Find(y); if(a > b) pre[b] = a; else pre[a] = b; } int main(void) { int n; while(cin >> n) { memset(cur, 0, sizeof(cur)); for(int i = 1; i <= n; i++) scanf("%d", &a[i]), pre[i] = i; pre[n+1] = n+1; int q; scanf("%d", &q); while(q--) { int cmd, x, y; scanf("%d%d", &cmd, &x); if(cmd == 1) { scanf("%d", &y); while(y) { int t = Find(x); if(t == n+1) break; if(a[t]-cur[t] >= y) { cur[t] += y; y = 0; } else { y -= a[t]-cur[t]; cur[t] = a[t]; join(t, t+1); } x = t; } } else printf("%d\n", cur[x]); } } return 0; }