Cdoeforce 371D. Vessels

[IMPLEMENT]
做了一個類似DISJOINT SET的優化
複雜度應該很像DISJOINT SET吧? XDD

#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<cstring>
#include<vector>
#define min(x,y) (((x)>(y)) ? (y):(x))
#define max(x,y) (((x)>(y)) ? (x):(y))
#define LL long long int
using namespace std;
#define NN 200000
int next[NN+1];
LL cap[NN+1];
LL vol[NN+1];
int n;
LL fillwater(int d,LL ww)
{
    if(d==n+1) return 0;
    if(ww>cap[d]-vol[d])
    {
        ww-=cap[d]-vol[d];
        vol[d]=cap[d];
        return ww;
    }
    else
    {
        vol[d]+=ww;
        return 0;
    }
}
int findnext(int d)
{
    if(d>=n) return n+1;
    int res=next[d];
    while(vol[res]>=cap[res])
        res=next[res];
    next[d]=res;
    return res;
}
int main()
{
    scanf("%d",&n);
    memset(vol,0,sizeof(vol));
    for(int lx=1;lx<=n;lx++)
        scanf("%I64d",&cap[lx]);
    cap[n+1]=1;
    for(int lx=1;lx<=n;lx++)
        next[lx]=lx+1;
    int Q;scanf("%d",&Q);
    while(Q--)
    {
        int cmd,a;
        LL b;
        scanf("%d",&cmd);
        if(cmd==1)
        {
            scanf("%d %I64d",&a,&b);
            for(int lx=a;b>0;lx=findnext(lx))
                b=fillwater(lx,b);
        }
        else
        {
            scanf("%d",&a);
            printf("%I64d\n",vol[a]);
        }

    }
    return 0;
}