CodeForces722C-白红宇

CodeForces722C

阅读量：5290 次

发布时间：2019-06-14

本文共 1314 字，大约阅读时间需要 4 分钟。

其实这个题我是不大会的....我一直在想怎么正面突破,然后我就冇了.

康了康\(dalao\)们的做法,发现这个题反着做是个很简单的题.

你考虑把删除操作换成倒着加入,然后就变成了一个序列合并问题.

每次加入一个数,只需要向左向右分别判断是否已经加入过数字,

如果加入过,就合并两个并查集,否则什么都不做.

同时维护一下并查集的权值——区间和.(体现在并查集上是子树和.)

最后倒序输出答案即可,不要忘记最后全部删除完成之后是\(0\).

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          #define int long longusing 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\n" , ans[i] ) ; puts ("0") ; system ("pause") ; return 0 ;}