（并查集）codeforces

原题链接：http://codeforces.com/contest/722/problem/C

题意：给一条数列，现在要来破坏这个数列，给出一个依次破坏数列中元素的顺序。每破坏一个输出当前数列最长连续子序列的和。

分析：

一开始感觉可以用线段树写，写好build后，感觉写的好烦。仔细想了下题目中的关系，其实就是一开始一群数字待在一起，然后拆开，其实就是并查集的逆过程，只需要把顺序倒过来进行一次并查集就行了。

用rank数组记录每个集合的和，用一个flag数组被个位置是否被破坏过。如果两边有被破坏的就合并两边的。需要处理1和n的边界。

代码：

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <string>
  4 #include <vector>
  5 #include <map>
  6 #include <set>
  7 #include <queue>
  8 #include <cstring>
  9 
 10 using namespace std;
 11 
 12 
 13 typedef long long ll;
 14 typedef unsigned long long ull;
 15 #define inf (0x3f3f3f3f)
 16 #define lnf (0x3f3f3f3f3f3f3f3f)
 17 #define eps (1e-8)
 18 int sgn(double a){return a < -eps ? -1 : a < eps ? 0 : 1 ;}
 19 
 20 //-------------------------------------------------
 21 
 22 const int maxn = 100000+10;
 23 int par[maxn];
 24 ll rank[maxn];
 25 
 26 void init(int n){
 27     for(int i=1;i<=n;i++){
 28         par[i]=i;
 29         rank[i]=0;
 30     }
 31 }
 32 
 33 int findx(int x){
 34     return par[x]==x ? x : par[x]=findx(par[x]);
 35 }
 36 
 37 void unite(int x,int y){
 38     x = findx(x);
 39     y = findx(y);
 40     if(rank[x]>rank[y]){
 41         par[y]=x;
 42         rank[x]+=rank[y];
 43     }
 44     else{
 45         par[x]=y;
 46         rank[y]+=rank[x];
 47     }
 48 }
 49 
 50 
 51 ll num[maxn];
 52 int des[maxn];
 53 ll ans[maxn];
 54 bool flag[maxn]={0};
 55 
 56 void solve(){
 57     int n;
 58     scanf("%d",&n);
 59     init(n);
 60     for(int i=1;i<=n;i++){
 61         scanf("%lld",&num[i]);
 62     }
 63     for(int i=1;i<=n;i++){
 64         scanf("%d",&des[i]);
 65     }
 66     ll maxs=0;
 67     for(int i=n;i>=1;i--){
 68         ans[i]=maxs;
 69         if(des[i]==1){
 70             rank[des[i]]=num[des[i]];
 71             if(flag[des[i]+1]){
 72                 unite(des[i],des[i]+1);
 73             }
 74             flag[des[i]]=true;
 75             maxs=max(maxs,rank[findx(des[i])]);//这边需要特别注意，因为在记录rank的时候不知道记录到了哪个父节点，也就是说不知道是哪个祖先，需要先找祖先。所以不能直接rank[des[i]]，而应该用rank[findx(des[i])].
 76         }
 77         else if(des[i]==n){
 78             rank[des[i]]=num[des[i]];
 79             if(flag[des[i]-1]){
 80                 unite(des[i],des[i]-1);
 81             }
 82             flag[des[i]]=true;
 83             maxs=max(maxs,rank[findx(des[i])]);
 84         }
 85         else{
 86             rank[des[i]]=num[des[i]];
 87             if(flag[des[i]+1]){
 88                 unite(des[i],des[i]+1);
 89             }
 90             if(flag[des[i]-1]){
 91                 unite(des[i],des[i]-1);
 92             }
 93             flag[des[i]]=true;
 94             maxs=max(maxs,rank[findx(des[i])]);
 95 
 96         }
 97         
 98     }
 99     for(int i=1;i<=n;i++){
100         printf("%lld
",ans[i] );
101     }
102 
103 }
104 
105 
106 
107 int main(){
108 
109 #ifndef ONLINE_JUDGE
110     freopen("1.in","r",stdin);
111     //freopen("1.out","w",stdout);
112 #endif
113 
114     solve();
115 }