Codeforces 371(#218 Div2 only) D. Vessels

問題

n枚の皿があって、i番目の皿の容量はa[i]リットル。
i番目の皿に水を注いで、容量を超えた分はi+1番目の皿に溢れる。（i+1番目の皿も一杯ならi+2番目に……となる）

n番目の皿から溢れた水は捨てられる。

次のクエリがm個来るので答えよ。

• i番目の皿にxリットルの水を注ぐ
• i番目の皿の水の容量を答える

制約条件

n≦2*10^5
m≦2*10^5
a[i]≦10^9

方針

i番目の皿に注いだときに入る皿を、union-find的な構造を使って実装すればはやい。
ならし計算量でlog nとかそれくらい。

それ以外の操作は愚直でいい。
皿が一杯になる回数は全部で高々n回だし、クエリはm個しかないから。

ソースコード

const int N = 200001;
int p[N];
int to(int x){
	if(p[x] == x) return x;
	return p[x] = to(p[x]);
}
int n, a[N];
int m, b[N];

int main(){
	
	cin >> n;
	rep(i, n) cin >> a[i], p[i] = i;
	p[n] = n;
	
	cin >> m;
	while(m--){
		
		int type, t, x;
		cin >> type >> t;
		t--;
		
		if(type == 1){
			cin >> x;
			
			t = to(t);
			while(x > 0 && t < n){
				
				int pour = min(a[t] - b[t], x);
				
				b[t] += pour;
				x -= pour;
				
				if(b[t] == a[t]){
					p[t] = to(t + 1);
					t = to(t + 1);
				}
			}
		}
		else{
			cout << b[t] << endl;
		}
	}
	return 0;
}