发布时间: 2017年7月4日 20:58 最后更新: 2017年7月6日 22:23 时间限制: 1000ms 内存限制: 512M
描述给出一个 n(1≤n≤2×105) 个非负整数 a1,a2,...,an 的序列，你要按一定顺序毁灭序列的中的数，在每次毁灭一个数后，输出不包括已毁灭元素的子段的最大字段和（空子段的字段和视为0）
输入第一行输入一个整数 n 为序列的长度 第二行输入 n 个数 a1,a2,...,an(0≤ai≤109) 第三行输入一个1到 n 的整数的排列，为毁灭元素的顺序
输出输出 n 行，每一行包含一个整数，意义见题目描述
样例输入1 复制 4 1 3 2 5 3 4 1 2 样例输出1 5 4 3 0 样例输入2 复制 5 1 2 3 4 5 4 2 3 5 1 样例输出2 6 5 5 1 0 样例输入3 复制 8 5 5 4 4 6 6 5 5 5 2 8 7 1 3 4 6 样例输出3 18 16 11 8 8 6 6 0 提示第一个样例中：
第一次毁灭第三个元素，数组为`1 3 * 5`，最大字段和为5
第二次毁灭第四个元素，数组为`1 3 * *`，最大子段和为4
第三次毁灭第一个元素，数组为`* 3 * *`，最大子段和为3
第四次毁灭第二个元素，最大子段和为0
题解：这道题目正向处理并不好处理，而反着想却非常简单。
这里用到的知识是倒跑并查集，我们把操作逆向处理，删除一个元素的逆操作就是增加一个元素，当这个元素增加到这个序列里面的时候，只有可能影响到它两边的字段，因此，我们将这个元素加入序列时候，把两边字段并入到刚加入的元素中，形成一个新的字段，这个字段的和就是两侧字段和加该元素的值。并用这个新的字段和和max_ans做更新，然后得到此次操作的答案。
字段做并操作就是并查集的合并。
这样的话，把得到的答案逆序输出就可以了。
代码：
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> using namespace std; const int MAX = 2e5+8; int n; int a[MAX]; int stack[MAX]; long long out_stk[MAX]; int pt_sp; int sp = 0; int parent[MAX]; long long vis[MAX]; int find(int x){ while(x != parent[x]) x = parent[x]; return x; } void init(){ for(int i = 0;i < MAX;i++){ parent[i] = i; } } int main(){ while(~scanf("%d",&n)){ memset(vis,0,sizeof(vis)); init(); sp = 0; for(int i = 0;i < n;i++){ scanf("%d",&a[i]); } for(int i = 0;i < n;i++){ scanf("%d",&stack[sp++]); } pt_sp = 0; long long max_ans = 0; while(sp--){ out_stk[pt_sp++] = max_ans; int pos = stack[sp]-1; vis[pos] += a[pos]; if(pos > 0 && vis[pos-1]){ int p = find(pos-1); vis[pos] += vis[p]; parent[p] = pos; } if(pos < n-1 && vis[pos+1]){ int p = find(pos+1); vis[pos] += vis[p]; parent[p] = pos; } max_ans = max(max_ans,vis[pos]); } while(pt_sp--){ printf("%lld\n",out_stk[pt_sp]); } } return 0; }
