题目大意就是给长度为 n 一个数列，有 n 每次删除，每一次删除第 i 个位置上的数，求每一次删除后剩余不连续数列的最大区间和。
输入样例
4
1 3 2 5
3 4 1 2
输出样例
5
4
3
0
第二行是原来的数列，第三行是删除第 i 个数。
这道题的正解是用并查集来做。要将删除的顺序存下来，并倒序操作，这样就相当于每一次加上第 i 数。然后判断加上的数的左右两边是否有数，有就合并，并尝试用合并的新的区间和更新答案。对了，答案也要存下来，再倒序输出，才是真正的答案。
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + ;
ll a[maxn], b[maxn], sum[maxn], ans[maxn], maxm = -;
int p[maxn], n;
bool vis[maxn]; //vis[i]判断第i个位置上的数是否存在
void init() //并查集初始化：每一个点都是自己的父亲节点
{
for(int i = ; i < maxn; ++i) {sum[i] = ; p[i] = i;}
return;
}
int Find(int x)
{
return p[x] == x ? x : p[x] = Find(p[x]);
}
void merge(int x, int y) //合并
{
int px = Find(x), py = Find(y);
//肯定不联通
p[px] = py;
sum[py] += sum[px];
return;
}
int main()
{
init();
scanf("%d", &n);
for(int i = ; i <= n; ++i) scanf("%lld", &a[i]);
for(int i = ; i <= n; ++i) scanf("%lld", &b[i]);
for(int i = n; i > ; --i)
{
vis[b[i]] = ;
sum[b[i]] = a[b[i]];
if(vis[b[i] - ]) merge(b[i], b[i] - ); //左边是否有数
if(vis[b[i] + ]) merge(b[i], b[i] + ); //右边是否有数
if(sum[Find(b[i])] > maxm) maxm = sum[Find(b[i])]; //尝试更新最大区间和
ans[i - ] = maxm;
}
for(int i = ; i <= n; ++i) printf("%lld\n", ans[i]);
return ;
}