[Codeforces Round #218 (Div. 2) pD][Disjoint Set] Vessels

原題連結
一道並查集的頗直覺的題目
難點大概就只有在有沒有想到要用Disjoint Set去做吧......
對於已經滿的vessel i ，執行 fa[i] <- findset(i+1) ，直觀上就是將每個相鄰的滿vessel連接起來，已達到快速查詢可用vessel的效果。

細節上要注意水流到地上的case要做好，不然很容易WA或是TLE。

#include<cstdio>
#define LL long long
using namespace std;
const int maxn=200000+5;
int fa[maxn],cap[maxn],cur[maxn];
int findset(int x) {return x==fa[x]?x:fa[x]=findset(fa[x]);}
int main()
{
    int n,m;
    scanf("%d",&n);
    for(int i=0;i<n;i++) {fa[i]=i;scanf("%d",cap+i);}
    fa[n]=n;
    scanf("%d",&m);
    for(int i=0,type,a,b;i<m;i++)
    {
        scanf("%d",&type);
        if(type==1)
        {
            scanf("%d%d",&a,&b);a--;
            a=findset(a);
            for(;b && a!=n;)
            {
                if(cap[a]-cur[a]>b) cur[a]+=b,b=0;
                else // cap[a]-cur[a]<=b
                {
                    b-=cap[a]-cur[a];
                    cur[a]=cap[a];
                    fa[a]=findset(a+1);
                    a=findset(a);
                }
            }
        }
        else
        {
            scanf("%d",&a);a--;
            printf("%d\n",cur[a]);
        }
    }
}