CodeForces722C

CodeForces722C

其实这个题我是不大会的....我一直在想怎么正面突破,然后我就冇了.
康了康(dalao)们的做法,发现这个题反着做是个很简单的题.
你考虑把删除操作换成倒着加入,然后就变成了一个序列合并问题.
每次加入一个数,只需要向左向右分别判断是否已经加入过数字,
如果加入过,就合并两个并查集,否则什么都不做.
同时维护一下并查集的权值——区间和.(体现在并查集上是子树和.)
最后倒序输出答案即可,不要忘记最后全部删除完成之后是(0).

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <queue>
#include <map>
#define int long long

using std::max ;

const int N = 1e5 + 100 ;

int n , v[N] , p[N] , ans[N] , f[N] , s[N] , maxx , cnt ;

inline int getf (int x) { return f[x] == x ? x : f[x] = getf ( f[x] ) ; }

signed main () {
    scanf ("%lld" , & n ) ;
    for (int i = 1 ; i <= n ; ++ i) scanf ("%lld" , & v[i] ) ;
    for (int i = 1 ; i <= n ; ++ i) scanf ("%lld" , & p[i] ) ;
    for (int i = n ; i >= 1 ; -- i) {
        int cur = p[i] ;
        if ( ! f[cur] ) { f[cur] = cur ; s[cur] = v[cur] ; }
        int y = getf ( cur ) ;
        if ( cur - 1 >= 1 && f[cur-1] ) {
            int x = getf ( cur - 1 ) ;
            if ( x != y ) f[x] = y , s[y] += s[x] , s[x] = 0 ;
        }
        if ( cur + 1 <= n && f[cur+1] ) {
            int x = getf ( cur + 1 ) ;
            if ( x != y ) f[x] = y , s[y] += s[x] , s[x] = 0 ;
        }
        maxx = max ( maxx , s[cur] ) ; ans[++cnt] = maxx ;
    }
    for (int i = n - 1 ; i >= 1 ; -- i) printf ("%lld
" , ans[i] ) ;
    puts ("0") ; system ("pause") ; return 0 ;
}