[并查集+逆向思维]Codeforces Round 722C Destroying Array
Destroying Array
1 second
256 megabytes
standard input
standard output
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,在原删除顺序中表示全部删完了
标记添加过的元素
找现在这个元素的父亲
如果这个元素的右边被添加过了,就看它属于哪个连续的集合,再把当前这个集合加入并查集
更新孩子(当前这个元素的父亲)的父亲,并更新父亲的连续区间和
如果这个元素的左边被添加过了,与上同理
最后看看这个元素属于哪个并查集
比较上一个答案和现在这个并查集的答案,选一个最大的作为当前答案
(写了这题后发现并查集的模板并不像记忆中的那么复杂...)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int amn=1e5+;
int n;
ll sum[amn],ans[amn];
bool used[amn];
int pre[amn],a[amn],order[amn];
void init(){
memset(used,,sizeof used);
for(int i=;i<=n;i++)pre[i]=i,sum[i]=a[i]; ///一开始它们的父亲是它们本身,它们的连续区间和是它们本身
}
int fd(int i){
return i==pre[i]?i:pre[i]=fd(pre[i]);
}
void add(int fa,int cd){
pre[cd]=fa; ///更新孩子的父亲
sum[fa]+=sum[cd]; ///更新父亲的连续区间和
}
int main(){
ios::sync_with_stdio();
cin>>n;
a[]=;
for(int i=;i<=n;i++){
cin>>a[i];
}
for(int i=n;i>=;i--){
cin>>order[i]; ///题目给的删除顺序,现在我们考虑加入顺序,所以逆向读入顺序
}
init();
ans[]=; ///最后一个没有加入元素,所以为0,在原删除顺序中表示全部删完了
int fa;
for(int i=;i<n;i++){
used[order[i]]=; ///标记添加过的元素
int ofa; ///找现在这个元素的父亲
if(used[order[i]+]){ ///如果这个元素的右边被添加过了,就看它属于哪个连续的集合,再把当前这个集合加入并查集
ofa=fd(order[i]);
fa=fd(order[i]+);
add(fa,ofa);
}
if(used[order[i]-]){ ///如果这个元素的左边被添加过了,与上同理
ofa=fd(order[i]);
fa=fd(order[i]-);
add(fa,ofa);
}
ofa=fd(order[i]); ///最后看看这个元素属于哪个并查集
ans[i]=max(ans[i-],sum[ofa]); ///比较上一个答案和现在这个并查集的答案,选一个最大的作为当前答案
}
for(int i=n-;i>=;i--){
printf("%lld\n",ans[i]);
}
}
/***
给你一个含n给个非负整数的数组,并给出一个它们依此被删除的顺序,要求每次连续区间和最大的那个是多少
一开始按题意模拟,果然TLE了,就发现如果把删除序列看成加入序列就很容易地可以算出连续区间和最大是多少,并可以用并查集来维护这个连续区间和
题目给的删除顺序,现在我们考虑加入顺序,所以逆向读入顺序
最后一个没有加入元素,所以为0,在原删除顺序中表示全部删完了
标记添加过的元素
找现在这个元素的父亲
如果这个元素的右边被添加过了,就看它属于哪个连续的集合,再把当前这个集合加入并查集
更新孩子(当前这个元素的父亲)的父亲,并更新父亲的连续区间和
如果这个元素的左边被添加过了,与上同理
最后看看这个元素属于哪个并查集
比较上一个答案和现在这个并查集的答案,选一个最大的作为当前答案
***/
最新文章
- 布里斯班Twilight Bay Run半程马拉松
- CJCMS系列--持久层对MangoDB的支持
- (翻译)理解Java当中的回调机制
- mybatis源码分析(1)——SqlSessionFactory实例的产生过程
- 开发设计模式(四) 代理模式(Proxy Pattern)
- nyoj 56 阶乘中素数的个数
- 由.Net类库提供的农历计算(C#农历)-获取当前日期的农历日期
- [序列化] SerializeHelper--序列化操作帮助类 (转载)
- BAPI总的数据库提交和回滚
- 汇总jQuery的61种选择器及示例
- Java 8 Learn Notes - Streams
- 在C#中几种常见数组复制方法的效率对比
- JAVA之旅(三十五)——完结篇,终于把JAVA写完了,真感概呐!
- 微信小程序--家庭记账本开发--06
- Python 进度条原理
- JVM总括四-类加载过程、双亲委派模型、对象实例化过程
- Redis 安装、配置、集群
- ATX 安卓设备 WiFi 统一管理以及设备自动化测试
- 【Javascript第二重境界】序
- C#中IDisposable的用法