codeforces 722C Destroying Array 【线段树好题】
题意：求按照序列删除之后的当前还剩下的数列中的最长的连续的子序列和
分析样例来说明白好了
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;
}
腾讯成长空间 5981人发布
投递美团等公司9个岗位