CFR 371 D. Vessels ( Union Find )

Problem - 371D - Codeforces
細節需要想一下下，怎麼快速存取下一個非滿的盤子的下標。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 5;
const int MAXA = 1e9 + 9;
const int MAXM = 2e5 + 5;

int n;
int a[ MAXN ], f[ MAXN ];
int m;

struct UnionFind{
    int fa[ MAXN ];
    void init(int z){
        for(int i = 1; i <= z; ++i)
            fa[ i ] = i;
    }
    int find(int x){ return fa[ x ] == x ? x : fa[ x ] = find( fa[ x ] ); }
    bool unite(int x, int y){
        int a = find( x );
        int b = find( y );
        if( a == b ) return false;
        fa[ a ] = b; return true;
    }
} uf;

int main(){
    scanf("%d", &n);
    uf.init( n );
    for(int i = 1; i <= n; ++i)
        scanf("%d", &a[ i ]);
    scanf("%d", &m);
    for(int i = 0; i < m; ++i){
        int op; scanf("%d", &op);
        if( op == 1 ){
            int k, x; scanf("%d%d", &k, &x);
            int p = uf.find( k );
            while( p <= n && f[ p ] + x >= a[ p ] ){
                x -= a[ p ] - f[ p ];
                if( p - k ) uf.unite( p - 1, p );
                f[ p ] = a[ p ];
                ++p;
            }
            f[ p ] += x;
        } else{
            int k; scanf("%d", &k);
            printf("%d\n", f[ k ]);
        }
    }
    return 0;
}