【bzoj4094】【洛谷3097】Optimal Milking

假的，假的，都是假的。

题意是最大点独立集还要算贡献，写个网络流岂不是GG？

其实这个也就是奇偶不能选而已……所以无外乎这么四种情况：

1. 左开右闭
2. 左闭右开
3. 都闭
4. 都开

线段树按照套路维护一下就好了。

#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<<][],n,m;

ll ans=;

inline int read(){

    int f=,x=;char ch;

    do{ch=getchar();if(ch=='-')f=-;}while(ch<''||ch>'');

    do{x=x*+ch-'';ch=getchar();}while(ch>=''&&ch<='');

    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=;i<;i++)

        f[o][i]=max(f[lson][i&]+f[rson][+(i&)],f[lson][(i&)+]+f[rson][i&],f[lson][(i&)+]+f[rson][i&]);

}

void build(int o,int l,int r){

    if(l==r){f[o][]=read();return;}

    int mid=(l+r)>>;

    build(lson,l,mid);build(rson,mid+,r);

    pushup(o);

}

void change(int o,int l,int r,int q,int v){

    if(l==r){f[o][]=v;return;}

    int mid=(l+r)>>;

    if(q<=mid)change(lson,l,mid,q,v);

    else change(rson,mid+,r,q,v);

    pushup(o);

}

int main(){

    n=read();m=read();

    build(,,n);

    while(m--){

        int x=read(),y=read();

        change(,,n,x,y);

        ans+=max(f[][],f[][],f[][],f[][]);

    }

    cout<<ans<<endl;

}