思路:用并查集维护,如果当前容器没有满,就指向自己,否则指向下一个容器。
这样就可以快速 find 到下一个没有满的容器,从而模拟询问 1。
代码:
void solve(){
int n;
cin >> n;
vector<int>p(n + 1), a(n + 1), c(n + 1);
for(int i = 1;i <= n;i ++){
cin >> a[i];
p[i] = i;
}
int m;
cin >> m;
while(m --){
int op;
cin >> op;
if(op == 1){
int pos, val;
cin >> pos >> val;
int id = p[pos];
while(c[id] + val >= a[id] && id <= n){
val -= (a[id] - c[id]);
c[id] = a[id];
id ++;
}
if(id <= n)
c[id] += val;
for(int j = p[pos];j < id;j ++)
p[j] = id;
p[pos] = id;
}
else{
int pos;
cin >> pos;
cout << c[pos] << endl;
}
}
}