记录编号	90481	评测结果	AAAAAAAAAAA
题目名称	最优挤奶法	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.356 s
提交时间	2014-03-07 21:49:18	内存使用	6.12 MiB

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<deque>
using namespace std;
const int SIZEN=40010;
typedef long long ll;
class SEGMENT{
public:
	int left,right;
	int ls,rs;
	ll lr,nlr,lnr,nlnr;//lr是两端都开,nlr是右开左不开,etc
	SEGMENT(){
		lr=nlr=lnr=nlnr=0;
	}
};
SEGMENT tree[SIZEN*3];
int tot=0;
ll M[SIZEN]={0};
inline ll max(ll a,ll b,ll c){
	return max(a,max(b,c));
}
inline ll max(ll a,ll b,ll c,ll d){
	return max(max(a,b),max(c,d));
}
void update(int root){
	SEGMENT &now=tree[root];
	if(now.left==now.right){//叶子节点
		now.lr=M[now.left];
		now.nlr=now.lnr=now.nlnr=0;
	}
	else{//联合算
		SEGMENT &lson=tree[now.ls],&rson=tree[now.rs];
		now.lr=max(lson.lr+rson.nlr,lson.lnr+rson.lr,lson.lnr+rson.nlr);
		now.nlr=max(lson.nlr+rson.nlr,lson.nlnr+rson.lr,lson.nlnr+rson.nlr);
		now.lnr=max(lson.lr+rson.nlnr,lson.lnr+rson.lnr,lson.lnr+rson.nlnr);
		now.nlnr=max(lson.nlr+rson.nlnr,lson.nlnr+rson.lnr,lson.nlnr+rson.nlnr);
	}
}
int build(int x,int y){
	int pos=tot++;
	SEGMENT &now=tree[pos];
	now.left=x,now.right=y;
	if(x<y){
		int mid=(x+y)>>1;
		now.ls=build(x,mid);
		now.rs=build(mid+1,y);
	}
	update(pos);
	return pos;
}
void nodechange(int root,int x){//改M[x],对节点root
	SEGMENT &now=tree[root];
	if(now.left<now.right){
		int mid=(now.left+now.right)>>1;
		if(x<=mid) nodechange(now.ls,x);
		else nodechange(now.rs,x);
	}
	update(root);
}
void change(int x,ll t){//M[x]=t
	M[x]=t;
	nodechange(0,x);
}
ll daymax(void){
	return max(tree[0].lr,tree[0].lnr,tree[0].nlr,tree[0].nlnr);
}
int N,D;
void work(void){
	ll ans=0,m;
	int k;
	for(int i=1;i<=D;i++){
		scanf("%d%lld",&k,&m);
		change(k,m);
		ans+=daymax();
	}
	printf("%lld\n",ans);
}
void read(void){
	scanf("%d%d",&N,&D);
	for(int i=1;i<=N;i++) scanf("%lld",&M[i]);
}
int main(){
	freopen("optmilk.in","r",stdin);
	freopen("optmilk.out","w",stdout);
	read();
	build(1,N);
	work();
	return 0;
}