codeforces 722C Destroying Array 【线段树好题】

codeforces722C

题意：求按照序列删除之后的当前还剩下的数列中的最长的连续的子序列和

分析样例来说明白好了

5
1 2 3 4 5
4 2 3 5 1

删除的顺序是4，2，3，5，1

第一轮：数列变成了1 2 3 & 5（最大的连续子段和：1+2+3=6）

第二轮：数列变成了1 & 3 & 5（最大的连续子段和：5）

第三轮：数列变成了1 & & & 5（最大的连续子段和：5）

第四轮：数列变成了1 & & & &（最大的连续子段和：1）

第五轮：数列变成了& & & & &（最大的连续子段和：0）

很经典的线段树思路：维护区间和：还需要维护最长的左边的连续的区间和，最长的右边的连续的区间和

那么，我们需要一个标记flag：当前的区间是不是满员的（如果满员，那么才会连续）

所以，我们的根节点，在维护自己的时候，是这样考虑连续函数的情况的：

根节点的连续区间和=max【左儿子的根节点的连续区间和，右儿子的根节点的连续区间和，左儿子的最长的右边+右儿子最长的左边】

	t[rt].ms=max(t[rt<<1].ms,t[rt<<1|1].ms);
	t[rt].ms=max(t[rt].ms,t[rt<<1|1].ls+t[rt<<1].rs);

如果左儿子当前是满员的，那么说明左右两边是连续的，所以还需要加上右儿子的左边

	t[rt].ls=t[rt<<1].ls;
	if (t[rt<<1].mark) t[rt].ls+=t[rt<<1|1].ls;

	t[rt].rs=t[rt<<1|1].rs;
	if (t[rt<<1|1].mark) t[rt].rs+=t[rt<<1].rs;

	if (!t[rt<<1].mark||!t[rt<<1|1].mark) t[rt].mark=0;

#include<bits/stdc++.h>
using namespace std;

#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL __int64
const int maxn=1e5+50;
int n;
LL a[maxn];

struct node{
	int l,r,c;
	LL ls,rs,ms;
	int mark;
}t[maxn<<3];

void build(int l,int r,int rt){
	t[rt].l=l;
	t[rt].r=r;
	t[rt].c=r-l+1;
	t[rt].mark=1;
	if (l==r){
		t[rt].ls=t[rt].rs=t[rt].ms=a[l];
		return;
	}
	int m=(l+r)>>1;
	build(lson);
	build(rson);
	t[rt].ls=t[rt].rs=t[rt].ms=t[rt<<1].ms+t[rt<<1|1].ms;
}

void update(int L,int R,int l,int r,int rt){
	if (L==l&&R==r){
		t[rt].ls=t[rt].rs=t[rt].ms=0;
		t[rt].mark=0;
		return;
	}
	int m=(l+r)>>1;
	if (R<=m) update(L,R,lson);
	else if (L>m) update(L,R,rson);
	
	t[rt].ls=t[rt<<1].ls;
	if (t[rt<<1].mark) t[rt].ls+=t[rt<<1|1].ls;
	
	t[rt].rs=t[rt<<1|1].rs;
	if (t[rt<<1|1].mark) t[rt].rs+=t[rt<<1].rs;
	
	t[rt].ms=max(t[rt<<1].ms,t[rt<<1|1].ms);
	t[rt].ms=max(t[rt].ms,t[rt<<1|1].ls+t[rt<<1].rs);
	
	if (!t[rt<<1].mark||!t[rt<<1|1].mark) t[rt].mark=0;
}

int main(){
	//freopen("input.txt","r",stdin);
	int n,x;
	while(scanf("%d",&n)!=EOF){
		for(int i=1;i<=n;i++) scanf("%I64d",&a[i]);
		build(1,n,1);
		for(int i=1;i<=n;i++){
			scanf("%d",&x);
			update(x,x,1,n,1);
			printf("%I64d\n",t[1].ms);
		}
	}
	return 0;
}