题目大意：给定n个点排成一排，每个点有一个点权，多次改变某个点的点权并将最大点独立集计入答案，输出最终的答案 开一个线段树，每个点记录四个信息： 区间左端点不选，右端点也不选的最大值 区间左端点选择，右端点不选的最大值 区间左端点不选，，右端点选择的最大值 区间左端点选择，右端点也选择的最大值 然后合并时讨论一下就行了
;struct abcd{int f[2][2];/*f[0][0]-两侧都不选f[1][0]-左侧选，右侧不选f[0][1]-左侧不选，右侧选f[1][1]-左右都选*/abcd() {}abcd(int x){f[0][0]=f[1][0]=f[0][1]=0;f[1][1]=x;}friend abcd operator + (const abcd &x,const abcd &y){abcd re;re.f[0][0]=max(max(x.f[0][1]+y.f[0][0],x.f[0][0]+y.f[1][0]),x.f[0][0]+y.f[0][0]);re.f[1][0]=max(max(x.f[1][0]+y.f[0][0],x.f[1][0]+y.f[1][0]),x.f[1][1]+y.f[0][0]);re.f[0][1]=max(max(x.f[0][0]+y.f[0][1],x.f[0][1]+y.f[0][1]),x.f[0][0]+y.f[1][1]);re.f[1][1]=max(max(x.f[1][0]+y.f[0][1],x.f[1][1]+y.f[0][1]),x.f[1][0]+y.f[1][1]);return re;}};struct Segtree{Segtree *ls,*rs;abcd sta;void* operator new (size_t){static Segtree mempool[M<<1],*C=mempool;return C++;}void Push_Up(){sta=ls->sta+rs->sta;}void Build_Tree(int x,int y,int a[]){int mid=x+y>>1;if(x==y){sta=abcd(a[mid]);return ;}(ls=new Segtree)->Build_Tree(x,mid,a);(rs=new Segtree)->Build_Tree(mid+1,y,a);Push_Up();}void Modify(int x,int y,int pos,int val){int mid=x+y>>1;if(x==y){sta=abcd(val);return ;}if(pos<=mid)ls->Modify(x,mid,pos,val);elsers->Modify(mid+1,y,pos,val);Push_Up();}/*abcd Get_Ans(int x,int y,int l,int r){int mid=x+y>>1;if(x==l&&y==r)return sta;if(r<=mid)return ls->Get_Ans(x,mid,l,r);if(l>mid)return rs->Get_Ans(mid+1,y,l,r);return ls->Get_Ans(x,mid,l,mid) + rs->Get_Ans(mid+1,y,mid+1,r) ;}*/}*tree=new Segtree;int n,m,a[M];long long ans=0;int main(){int i,x,y;cin>>n>>m;for(i=1;i<=n;i++)scanf(“%d”,&a[i]);tree->Build_Tree(1,n,a);for(i=1;i<=m;i++){scanf(“%d%d”,&x,&y);tree->Modify(1,n,x,y);ans+=max(max(tree->sta.f[0][0],tree->sta.f[0][1]),max(tree->sta.f[1][0],tree->sta.f[1][1]));}cout<<ans<<endl;return 0;}
人生如果错了方向，停止就是进步”。
