Vessels

Codeforces Round #218 (Div. 2) D:http://codeforces.com/problemset/problem/371/D

题意：就是有一些盘子，盘子里可以装水，这些盘子是从上到下一次排开的，然后会有一些操作1,p ,x，表示在第p个盘子里加入水x，如果这个盘子装不下，水就会流向下一个盘子。2 p，表示查询第p个盘子里有多少水。

题解：这一题用到并查集是真的没有想到，也很难想到。水向下流的过程，就相当于儿子找父亲的过程，然后用并查集直接模拟出来，就可以了。具体可以看看代码。一开始，往线段树和树状数组上想，总是想不到解决办法。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=2e5+10;
int f[N],val[N],a[N];
int n,m,t1,t2,t3;
void init(){
   memset(val,0,sizeof(val));
   memset(a,0,sizeof(a));
   for(int i=1;i<=n;i++)
    f[i]=i;
}
int Find(int x){
   int s;
   for(s=x;s!=f[s];s=f[s]);
   while(s!=x){
    int temp=f[x];
    f[x]=s;
    x=temp;
   }
   return s;
}
int main(){
    while(~scanf("%d",&n)){
         init();
        for(int i=1;i<=n;i++){
            scanf("%d",&val[i]);
            a[i]=val[i];
        }
        scanf("%d",&m);
        for(int i=1;i<=m;i++){
            scanf("%d%d",&t1,&t2);
            if(t1==1){
                scanf("%d",&t3);
                int r=Find(t2);
                while(t3>0){
                    if(val[r]>=t3){
                        val[r]-=t3;
                        break;
                    }
                    else{
                        t3-=val[r];
                        val[r]=0;
                        int temp=r++;
                        if(r>n)break;
                         else r=Find(r);
                        f[temp]=r;
                    }
                }
            }
            else
                printf("%d
",a[t2]-val[t2]);
        }
    }
}