首页 > 代码库 > codeforces772C

codeforces772C

2024-08-15 14:06:34   220人阅读

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

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

技术分享
  1 #include <cstdio>  2   3 #include <algorithm>  4   5 using namespace std;  6   7 typedef long long LL;  8   9 const int maxn=100000; 10  11 int n; 12  13 int i; 14  15 int a[maxn+10]; 16  17 int b[maxn+10]; 18  19 LL res[maxn+10]; 20  21 struct node{ 22     int l,r; 23     LL sum; 24     int lflag,rflag; 25     LL lval,rval; 26     bool f; 27 }tree[maxn*4+10]; 28  29 void push_up(int id){ 30    int llf=tree[id<<1].lflag; 31    int lrf=tree[id<<1].rflag; 32    int rlf=tree[(id<<1)+1].lflag; 33    int rrf=tree[(id<<1)+1].rflag; 34    if(lrf&&rlf){ 35       tree[id].sum=max(max(tree[id<<1].rval+tree[(id<<1)+1].lval,tree[id<<1].sum),tree[(id<<1)+1].sum); 36       tree[id].lflag=llf; 37       tree[id].rflag=rrf; 38       if(llf){ 39       if(tree[id<<1].f) 40       tree[id].lval=tree[id<<1].lval+tree[(id<<1)+1].lval; 41       else tree[id].lval=tree[id<<1].lval; 42       } else { 43           tree[id].lval=0; 44       } 45       if(rrf){ 46       if(tree[(id<<1)+1].f){ 47       tree[id].rval=tree[(id<<1)].rval+tree[(id<<1)+1].rval; 48       } 49       else tree[id].rval=tree[(id<<1)+1].rval; 50       } else { 51          tree[id].rval=0; 52       } 53       tree[id].f=tree[(id<<1)].f&&tree[(id<<1)+1].f; 54    }else if(!lrf||!rlf){ 55       if(tree[id<<1].sum>tree[(id<<1)+1].sum){ 56             tree[id].sum=tree[id<<1].sum; 57             tree[id].lflag=llf; 58             tree[id].rflag=rrf; 59             if(!llf) 60             tree[id].lval=0; 61             else tree[id].lval=tree[id<<1].lval; 62             if(!rrf) 63             tree[id].rval=0; 64             else 65             tree[id].rval=tree[(id<<1)+1].rval; 66             tree[id].f=0; 67       } else if(tree[id<<1].sum<tree[(id<<1)+1].sum){ 68              tree[id].sum=tree[(id<<1)+1].sum; 69              tree[id].lflag=llf; 70              tree[id].rflag=rrf; 71              if(!llf) 72              tree[id].lval=0; 73              else tree[id].lval=tree[id<<1].lval; 74              if(!rrf) 75              tree[id].rval=0; 76              else 77              tree[id].rval=tree[(id<<1)+1].rval; 78              tree[id].f=0; 79       } else if(tree[id<<1].sum==tree[(id<<1)+1].sum){ 80              tree[id].sum=tree[id<<1].sum; 81              tree[id].lflag=llf; 82              tree[id].rflag=rrf; 83              if(!llf) 84              tree[id].lval=0; 85              else tree[id].lval=tree[id<<1].lval; 86              if(!rrf) 87              tree[id].rval=0; 88              else 89              tree[id].rval=tree[(id<<1)+1].rval; 90              tree[id].f=0; 91       } 92  93    } 94 } 95  96 void build(int id,int l,int r){ 97      if(l==r){ 98        tree[id].l=tree[id].r=l; 99        tree[id].sum=0;100        tree[id].lflag=tree[id].rflag=0;101        tree[id].lval=tree[id].rval=0;102        tree[id].f=0;103        return ;104      }105      int mid=(l+r)>>1;106      build(id<<1,l,mid);107      build((id<<1)+1,mid+1,r);108      push_up(id);109 }110 111 void update(int id,int l,int r,int x,int val){112         if(l==r){113         tree[id].sum+=(LL)val;114         tree[id].lflag=tree[id].rflag=1;115         tree[id].lval=tree[id].rval=val;116         tree[id].f=1;117         return ;118      }119      int mid=(l+r)>>1;120      if(x<=mid){121        update(id<<1,l,mid,x,val);122      } else {123        update((id<<1)+1,mid+1,r,x,val);124      }125      push_up(id);126 }127 128 int main()129 {130     scanf("%d",&n);131     build(1,1,n);132     for(i=1;i<=n;i++){133         scanf("%d",&a[i]);134     }135     for(i=1;i<=n;i++){136         scanf("%d",&b[i]);137     }138     for(i=n;i>=2;i--){139           update(1,1,n,b[i],a[b[i]]);140           res[i]=tree[1].sum;141     }142     for(int i=2;i<=n+1;i++){143        printf("%I64d\n",res[i]);144     }145     return 0;146 }
View Code

 

codeforces772C


联系
我们