CFR 305 B. Mike and Feet ( UnionFind )

Problem - 547b - Codeforces
題意：
給一組數列。對於 x for each 1 to N，輸出數列中，屬於連續 x 個元素構成的區間裡最小值的最大值。
解法：
由大的數字至小，每次將大的數字和左右的數字於並查集結構中，以位置為單位並在一起，若且為若左右的數比它本身大。這麼一來，就能貪心地將大的數字留給盡量大的區間更新最大值。

struct UF{
    vi fa;
    vi size;
    UF( int sz ){
        fa = vi( sz );
        size = vi( sz );
        for( int i = 0; i < sz; ++i )
            fa[ i ] = i,
            size[ i ] = 1;
    }
    int find( int x ){
        if( fa[ x ] == x )
            return x;
        return fa[ x ] = find( fa[ x ] );
    }
    int unite( int x, int y ){
        int a = find( x );
        int b = find( y );
        if( a == b )
            return 0;
        size[ a ] += size[ b ];
        fa[ b ] = a;
        return 1;
    }
};

int N;
vi A;

void init(){
    cin >> N;
    A = vi( N );
    for( int i = 0; i < N; ++i )
        cin >> A[ i ];
}

vi ans;

void preprocess(){
    ans = vi( N + 1 );
    UF *uf = new UF( N );
    vp bear;
    for( int i = 0; i < N; ++i )
        bear.emplace_back( A[ i ], i );
    sort( bear.begin(), bear.end(), greater< pii >() );
    vi vis( N );
    for( int i = 0, ans_ptr = 1; i < N; ++i ){
        int v, p; tie( v, p ) = bear[ i ];
        vis[ p ] = 1;
        if( 0 <= p - 1 and vis[ p - 1 ] )
            uf->unite( p - 1, p );
        if( p + 1 < N and vis[ p + 1 ] )
            uf->unite( p, p + 1 );
        while( ans_ptr <= uf->size[ uf->find( p ) ] )
            ans[ ans_ptr++ ] = v;
    }
    delete uf;
}

void solve(){
    for( int i = 1; i <= N; ++i )
        cout << ans[ i ] << " \n"[ i == N ];
}