codeforces772C

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

给一段序列，给你去掉所有数字的顺序，输出每去掉一个数，当前联通的子序列的最大值。

倒着来，每次插入一个数，然后求联通的最大值，线段树每个节点标记一下，区间的左右是否插入了数字，还有如果有数字从左边/右边开始连续子序列的值，还有这个节点的区间是否连续。

 #include <cstdio>

 #include <algorithm>

 using namespace std;

 typedef long long LL;

 const int maxn=;

 int n;

 int i;

 int a[maxn+];

 int b[maxn+];

 LL res[maxn+];

 struct node{

     int l,r;

     LL sum;

     int lflag,rflag;

     LL lval,rval;

     bool f;

 }tree[maxn*+];

 void push_up(int id){

    int llf=tree[id<<].lflag;

    int lrf=tree[id<<].rflag;

    int rlf=tree[(id<<)+].lflag;

    int rrf=tree[(id<<)+].rflag;

    if(lrf&&rlf){

       tree[id].sum=max(max(tree[id<<].rval+tree[(id<<)+].lval,tree[id<<].sum),tree[(id<<)+].sum);

       tree[id].lflag=llf;

       tree[id].rflag=rrf;

       if(llf){

       if(tree[id<<].f)

       tree[id].lval=tree[id<<].lval+tree[(id<<)+].lval;

       else tree[id].lval=tree[id<<].lval;

       } else {

           tree[id].lval=;

       }

       if(rrf){

       if(tree[(id<<)+].f){

       tree[id].rval=tree[(id<<)].rval+tree[(id<<)+].rval;

       }

       else tree[id].rval=tree[(id<<)+].rval;

       } else {

          tree[id].rval=;

       }

       tree[id].f=tree[(id<<)].f&&tree[(id<<)+].f;

    }else if(!lrf||!rlf){

       if(tree[id<<].sum>tree[(id<<)+].sum){

             tree[id].sum=tree[id<<].sum;

             tree[id].lflag=llf;

             tree[id].rflag=rrf;

             if(!llf)

             tree[id].lval=;

             else tree[id].lval=tree[id<<].lval;

             if(!rrf)

             tree[id].rval=;

             else

             tree[id].rval=tree[(id<<)+].rval;

             tree[id].f=;

       } else if(tree[id<<].sum<tree[(id<<)+].sum){

              tree[id].sum=tree[(id<<)+].sum;

              tree[id].lflag=llf;

              tree[id].rflag=rrf;

              if(!llf)

              tree[id].lval=;

              else tree[id].lval=tree[id<<].lval;

              if(!rrf)

              tree[id].rval=;

              else

              tree[id].rval=tree[(id<<)+].rval;

              tree[id].f=;

       } else if(tree[id<<].sum==tree[(id<<)+].sum){

              tree[id].sum=tree[id<<].sum;

              tree[id].lflag=llf;

              tree[id].rflag=rrf;

              if(!llf)

              tree[id].lval=;

              else tree[id].lval=tree[id<<].lval;

              if(!rrf)

              tree[id].rval=;

              else

              tree[id].rval=tree[(id<<)+].rval;

              tree[id].f=;

       }

    }

 }

 void build(int id,int l,int r){

      if(l==r){

        tree[id].l=tree[id].r=l;

        tree[id].sum=;

        tree[id].lflag=tree[id].rflag=;

        tree[id].lval=tree[id].rval=;

        tree[id].f=;

        return ;

      }

      int mid=(l+r)>>;

      build(id<<,l,mid);

      build((id<<)+,mid+,r);

      push_up(id);

 }

 void update(int id,int l,int r,int x,int val){

         if(l==r){

         tree[id].sum+=(LL)val;

         tree[id].lflag=tree[id].rflag=;

         tree[id].lval=tree[id].rval=val;

         tree[id].f=;

         return ;

      }

      int mid=(l+r)>>;

      if(x<=mid){

        update(id<<,l,mid,x,val);

      } else {

        update((id<<)+,mid+,r,x,val);

      }

      push_up(id);

 }

 int main()

 {

     scanf("%d",&n);

     build(,,n);

     for(i=;i<=n;i++){

         scanf("%d",&a[i]);

     }

     for(i=;i<=n;i++){

         scanf("%d",&b[i]);

     }

     for(i=n;i>=;i--){

           update(,,n,b[i],a[b[i]]);

           res[i]=tree[].sum;

     }

     for(int i=;i<=n+;i++){

        printf("%I64d\n",res[i]);

     }

     return ;

 }