[并查集+逆向思维]Codeforces Round 722C Destroying Array

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int amn=1e5+5;
 5 int n;
 6 ll sum[amn],ans[amn];
 7 bool used[amn];
 8 int pre[amn],a[amn],order[amn];
 9 void init(){
10     memset(used,0,sizeof used);
11     for(int i=1;i<=n;i++)pre[i]=i,sum[i]=a[i];  ///一开始它们的父亲是它们本身,它们的连续区间和是它们本身
12 }
13 int fd(int i){
14     return i==pre[i]?i:pre[i]=fd(pre[i]);
15 }
16 void add(int fa,int cd){
17     pre[cd]=fa;             ///更新孩子的父亲
18     sum[fa]+=sum[cd];       ///更新父亲的连续区间和
19 }
20 int main(){
21     ios::sync_with_stdio(0);
22     cin>>n;
23     a[0]=0;
24     for(int i=1;i<=n;i++){
25         cin>>a[i];
26     }
27     for(int i=n;i>=1;i--){
28         cin>>order[i];          ///题目给的删除顺序,现在我们考虑加入顺序,所以逆向读入顺序
29     }
30     init();
31     ans[0]=0;                   ///最后一个没有加入元素,所以为0,在原删除顺序中表示全部删完了
32     int fa;
33     for(int i=1;i<n;i++){
34         used[order[i]]=1;       ///标记添加过的元素
35         int ofa;                ///找现在这个元素的父亲
36         if(used[order[i]+1]){   ///如果这个元素的右边被添加过了,就看它属于哪个连续的集合,再把当前这个集合加入并查集
37             ofa=fd(order[i]);
38             fa=fd(order[i]+1);
39             add(fa,ofa);
40         }
41         if(used[order[i]-1]){   ///如果这个元素的左边被添加过了,与上同理
42             ofa=fd(order[i]);
43             fa=fd(order[i]-1);
44             add(fa,ofa);
45         }
46         ofa=fd(order[i]);       ///最后看看这个元素属于哪个并查集
47         ans[i]=max(ans[i-1],sum[ofa]);  ///比较上一个答案和现在这个并查集的答案,选一个最大的作为当前答案
48     }
49     for(int i=n-1;i>=0;i--){
50         printf("%lld\n",ans[i]);
51     }
52 }
53 /***
54 给你一个含n给个非负整数的数组,并给出一个它们依此被删除的顺序,要求每次连续区间和最大的那个是多少
55 一开始按题意模拟,果然TLE了,就发现如果把删除序列看成加入序列就很容易地可以算出连续区间和最大是多少,并可以用并查集来维护这个连续区间和
56 题目给的删除顺序,现在我们考虑加入顺序,所以逆向读入顺序
57 最后一个没有加入元素,所以为0,在原删除顺序中表示全部删完了
58 标记添加过的元素
59 找现在这个元素的父亲
60 如果这个元素的右边被添加过了,就看它属于哪个连续的集合,再把当前这个集合加入并查集
61 更新孩子(当前这个元素的父亲)的父亲,并更新父亲的连续区间和
62 如果这个元素的左边被添加过了,与上同理
63 最后看看这个元素属于哪个并查集
64 比较上一个答案和现在这个并查集的答案,选一个最大的作为当前答案
65 ***/