建立线段树，维护区间左端点选/不选，右端点选/不选且不含有相邻两个同时选的最大值，合并时注意细节即可
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define mid (l+r>>1) 4 #define L (k<<1) 5 #define R (L+1) 6 int n,m,x,y; 7 long long ans; 8 struct ji{ 9 int a[4]; 10 }f[200005]; 11 ji up(ji x,ji y){ 12 ji z; 13 for(int i=0;i<4;i++)z.a[i]=0; 14 for(int i=0;i<4;i++) 15 for(int j=0;j<4;j++) 16 if ((i%2)||(j/2)) 17 z.a[i/2*2+j%2]=max(z.a[i/2*2+j%2],x.a[i]+y.a[j]); 18 return z; 19 } 20 void update(int k,int l,int r,int x,int y){ 21 if (l==r){ 22 f[k].a[0]=y; 23 return; 24 } 25 if (x<=mid)update(L,l,mid,x,y); 26 else update(R,mid+1,r,x,y); 27 f[k]=up(f[L],f[R]); 28 } 29 int main(){ 30 scanf("%d%d",&n,&m); 31 for(int i=1;i<=n;i++){ 32 scanf("%d",&x); 33 update(1,1,n,i,x); 34 } 35 for(int i=1;i<=m;i++){ 36 scanf("%d%d",&x,&y); 37 update(1,1,n,x,y); 38 ans+=f[1].a[0]; 39 } 40 printf("%lld",ans); 41 }