线段树
每个节点保存4个值，both表示左右端点都取，neither表示左右端点都不取，left表示只取左端点，right表示只取右端点。
维护的特殊姿势：
$cur$的$both=max(ls.l+rs.r，ls.both+rs.r，ls.l+rs.both)$
$cur$的$neither=max(ls.nei+rs.nei，ls.r+rs.nei，ls.nei+rs.l)$
$cur$的$left=max(ls.l+rs.l，ls.l+rs.nei，ls.both+ls.nei)$
$cur$的$right=max(ls.r+rs.r，ls.nei+rs.r，ls.nei+rs.both)$
1 #include<cstdio> 2 #include<algorithm> 3 #define LL long long 4 #define ls (cur<<1) 5 #define rs (cur<<1|1) 6 #define mid ((l+r)>>1) 7 using namespace std; 8 const int maxn=800010; 9 LL n,m,ans; 10 struct tree{ 11 LL both,l,r,nei; 12 }a[maxn]; 13 void read(LL &k){ 14 k=0; int f=1; char c=getchar(); 15 while (c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); 16 while ('0'<=c&&c<='9')k=k*10+c-'0',c=getchar(); 17 k*=f; 18 } 19 void pushup(int cur,int l,int r){ 20 if (l==r) return; 21 int t1=a[ls].both+a[rs].r,t2=a[ls].l+a[rs].both,t3=a[ls].l+a[rs].r, //both 22 t4=a[ls].l+a[rs].l,t5=a[ls].l+a[rs].nei,t6=a[ls].both+a[rs].nei, //left 23 t7=a[ls].r+a[rs].r,t8=a[ls].nei+a[rs].r,t9=a[ls].nei+a[rs].both, //right 24 t10=a[ls].nei+a[rs].nei,t11=a[ls].nei+a[rs].l,t12=a[ls].r+a[rs].nei; //neither 25 a[cur].both=max(max(t1,t2),t3); 26 a[cur].l=max(max(t4,t5),t6); 27 a[cur].r=max(max(t7,t8),t9); 28 a[cur].nei=max(max(t10,t11),t12); 29 } 30 void build(int cur,int l,int r){ 31 a[cur].l=0; a[cur].r=0; a[cur].nei=0; 32 if (l<r){ 33 build(ls,l,mid); 34 build(rs,mid+1,r); 35 } 36 else read(a[cur].both); 37 pushup(cur,l,r); 38 } 39 void update(int cur,int l,int r,int pos,int x){ 40 if (l==r) a[cur].both=x; 41 else{ 42 if (pos<=mid) update(ls,l,mid,pos,x); 43 else update(rs,mid+1,r,pos,x); 44 } 45 pushup(cur,l,r); 46 } 47 int main(){ 48 read(n); read(m); 49 build(1,1,n); 50 for (int i=1;i<=m;i++){ 51 LL x,y; read(x); read(y); 52 update(1,1,n,x,y); 53 ans+=max(max(max(a[1].both,a[1].nei),a[1].l),a[1].r); 54 } 55 printf("%lld ",ans); 56 return 0; 57 }