线段树

每个节点保存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
      
        2 #include
       
         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, //both22         t4=a[ls].l+a[rs].l,t5=a[ls].l+a[rs].nei,t6=a[ls].both+a[rs].nei, //left23         t7=a[ls].r+a[rs].r,t8=a[ls].nei+a[rs].r,t9=a[ls].nei+a[rs].both, //right24         t10=a[ls].nei+a[rs].nei,t11=a[ls].nei+a[rs].l,t12=a[ls].r+a[rs].nei; //neither25     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