建立线段树，维护区间左端点选/不选，右端点选/不选且不含有相邻两个同时选的最大值，合并时注意细节即可

1 #include
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 }