题目：Optimal Milking
思路：
线段树的单点修改区间查询。
每个节点维护4个值，及左右端点选或不选的最大和，用二进制存储，更新时分类讨论。
注意：使用long long类型。
代码：
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <cstring>
#include <map>
using namespace std;#define maxn 40000
#define inf (1<<29)
#define ll long longstruct Node {ll v[5];Node (ll x=0,ll y=0,ll z=0,ll u=0) {v[0]=x,v[1]=y,v[2]=z,v[3]=u;}
};int n,m;
int c[maxn+5];Node a[maxn*4+5];
int p,q;ll Max(ll x1=-inf,ll x2=-inf,ll x3=-inf,ll x4=-inf) {return max(max(x1,x2),max(x3,x4));
}ll gt(int o,int x,int y) {int lc=o*2,rc=o*2+1;return a[lc].v[x]+a[rc].v[y];
}void st(int o) {a[o].v[0]=Max(gt(o,0,0),gt(o,0,2),gt(o,1,0));a[o].v[1]=Max(gt(o,0,1),gt(o,0,3),gt(o,1,1));a[o].v[2]=Max(gt(o,2,2),gt(o,2,0),gt(o,3,0));a[o].v[3]=Max(gt(o,2,1),gt(o,2,3),gt(o,3,1));
}void make_tree(int o,int l,int r) {if(l==r) {a[o]=Node(0,-inf,-inf,c[l]);return ;}int lc=o*2,rc=o*2+1,mid=l+(r-l)/2;make_tree(lc,l,mid),make_tree(rc,mid+1,r);st(o);
}void update(int o,int l,int r) {if(l>p||r<p) return ;if(l==r) {a[o]=Node(0,-inf,-inf,q);return ;}int lc=o*2,rc=o*2+1,mid=l+(r-l)/2;update(lc,l,mid),update(rc,mid+1,r);st(o);
}int main() {scanf("%d%d",&n,&m);for(int i=1; i<=n; i++) scanf("%d",&c[i]);make_tree(1,1,n);ll ans=0;for(int i=1; i<=m; i++) {scanf("%d%d",&p,&q);update(1,1,n);ans+=Max(a[1].v[0],a[1].v[1],a[1].v[2],a[1].v[3]);}printf("%lld",ans);return 0;
}