codeforces 722C. Destroying Array

本文主要是介绍codeforces 722C. Destroying Array，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：传送门
线段树的维护和更新
这是网上一份代码，学习了

#include <bits/stdc++.h>
using namespace std;
#define N 100100
#define mod 1000000007
#define inf 2000000000000000ll
struct node{long long int l,r,sum;
}t[N];
bool flag[N];
int a[N],b[N];
long long int c[N];
int main(){int i,j,n,m;cin>>n;for(i=1;i<=n;i++){cin>>a[i];t[i].l=i;t[i].r=i;t[i].sum=a[i];}int x;for(i=1;i<=n;i++)cin>>b[i];long long int Max=0;for(i=n;i>0;i--){x=b[i];flag[x]=1;if(flag[x-1]){t[x].l=t[x-1].l;t[t[x].l].sum=t[t[x-1].l].sum+t[t[x].r].sum;t[x].sum=t[t[x].l].sum;if(flag[x+1]) t[t[x].l].r=t[x+1].r;else t[t[x].l].r=t[x].r;}if(flag[x+1]){t[x].r=t[x+1].r;t[t[x].r].l=t[x].l;t[t[x].r].sum=t[t[x].r].sum+t[t[x].l].sum;t[t[x].l].sum=t[t[x].r].sum;if(flag[x-1]) t[t[x].r].l=t[x].l;}Max=max(Max,t[t[x].l].sum);Max=max(Max,t[t[x].r].sum);c[i]=Max;}for(i=2;i<=n;i++)cout<<c[i]<<endl;cout<<"0"<<endl;return 0;
}

这篇关于codeforces 722C. Destroying Array的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---