假的，假的，都是假的。
题意是最大点独立集还要算贡献，写个网络流岂不是GG？
其实这个也就是奇偶不能选而已……所以无外乎这么四种情况：
- 左开右闭
- 左闭右开
- 都闭
- 都开
线段树按照套路维护一下就好了。
#include<bits/stdc++.h> #define N 50010 #define lson (o<<1) #define rson (o<<1|1) using namespace std; typedef long long ll; int f[N<<2][4],n,m; ll ans=0; inline int read(){ int f=1,x=0;char ch; do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9'); do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9'); return f*x; } inline int max(int a,int b,int c){return max(max(a,b),c);} inline int max(int a,int b,int c,int d){return max(max(a,b),max(c,d));} inline void pushup(int o){ for(int i=0;i<4;i++) f[o][i]=max(f[lson][i&2]+f[rson][2+(i&1)],f[lson][(i&2)+0]+f[rson][i&1],f[lson][(i&2)+1]+f[rson][i&1]); } void build(int o,int l,int r){ if(l==r){f[o][3]=read();return;} int mid=(l+r)>>1; build(lson,l,mid);build(rson,mid+1,r); pushup(o); } void change(int o,int l,int r,int q,int v){ if(l==r){f[o][3]=v;return;} int mid=(l+r)>>1; if(q<=mid)change(lson,l,mid,q,v); else change(rson,mid+1,r,q,v); pushup(o); } int main(){ n=read();m=read(); build(1,1,n); while(m--){ int x=read(),y=read(); change(1,1,n,x,y); ans+=max(f[1][0],f[1][1],f[1][2],f[1][3]); } cout<<ans<<endl; }