[并查集+逆向思维]Codeforces Round 722C Destroying Array
Destroying Array
You are given an array consisting of n non-negative integers a1, a2, ..., an.
You are going to destroy integers in the array one by one. Thus, you are given the permutation of integers from 1 to n defining the order elements of the array are destroyed.
After each element is destroyed you have to find out the segment of the array, such that it contains no destroyed elements and the sum of its elements is maximum possible. The sum of elements in the empty segment is considered to be 0.
The first line of the input contains a single integer n (1 ≤ n ≤ 100 000) — the length of the array.
The second line contains n integers a1, a2, ..., an (0 ≤ ai ≤ 109).
The third line contains a permutation of integers from 1 to n — the order used to destroy elements.
Print n lines. The i-th line should contain a single integer — the maximum possible sum of elements on the segment containing no destroyed elements, after first i operations are performed.
4
1 3 2 5
3 4 1 2
5
4
3
0
5
1 2 3 4 5
4 2 3 5 1
6
5
5
1
0
8
5 5 4 4 6 6 5 5
5 2 8 7 1 3 4 6
18
16
11
8
8
6
6
0
Consider the first sample:
- Third element is destroyed. Array is now 1 3 * 5. Segment with maximum sum 5 consists of one integer 5.
- Fourth element is destroyed. Array is now 1 3 * * . Segment with maximum sum 4 consists of two integers 1 3.
- First element is destroyed. Array is now * 3 * * . Segment with maximum sum 3 consists of one integer 3.
- Last element is destroyed. At this moment there are no valid nonempty segments left in this array, so the answer is equal to 0.
题意:给你一个含n给个非负整数的数组,并给出一个它们依此被删除的顺序,要求每次连续区间和最大的那个是多少
思路:一开始按题意模拟,果然TLE了,观察了一下样例就发现如果把删除序列看成加入序列就很容易地可以算出连续区间和最大是多少,并可以用并查集来维护这个连续区间和
题目给的删除顺序,现在我们考虑加入顺序,所以逆向读入顺序
最后一个没有加入元素,所以为0,在原删除顺序中表示全部删完了
标记添加过的元素
找现在这个元素的父亲
如果这个元素的右边被添加过了,就看它属于哪个连续的集合,再把当前这个集合加入并查集
更新孩子(当前这个元素的父亲)的父亲,并更新父亲的连续区间和
如果这个元素的左边被添加过了,与上同理
最后看看这个元素属于哪个并查集
比较上一个答案和现在这个并查集的答案,选一个最大的作为当前答案
(写了这题后发现并查集的模板并不像记忆中的那么复杂...)
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 ***/
查看45道真题和解析
投递腾讯等公司10个岗位 >
