记录编号	90805	评测结果	AAAAAAAAAAA
题目名称	最优挤奶法	最终得分	100
用户昵称	超级傲娇的AC酱	是否通过	通过
代码语言	C++	运行时间	0.310 s
提交时间	2014-03-09 21:43:00	内存使用	0.31 MiB

/*
Code Designed by Hao Chen
The King of Algorithm
*/
#include<cstdio>
#include<vector>
#include<cmath>
#include<cstdlib>
using namespace std;
long long Ans=0;
vector<int>M;
struct SgTree
{
	int L,R;
	int L_R,L_iR,iL_R,iL_iR;
	SgTree *Left,*Right;
	int val;
};
SgTree *Root=new SgTree;
SgTree *ConstNode=new SgTree;
void Build(int,int,SgTree *);
void Change(int,int,SgTree *);
int main()
{
	int n,m,k,i,d;
	freopen("optmilk.in","r",stdin);
	freopen("optmilk.out","w",stdout);
	scanf("%d %d",&n,&d);
	M.resize(n+1);
	for(i=1;i<=n;i++)
		scanf("%d",&M[i]);
	Build(1,n,Root);
	for(i=0;i<d;i++)
	{
		scanf("%d%d",&k,&m);
		Change(k,m,Root);
		Ans+=Root->val;
	}
	printf("%lld",Ans);
	return 0;
}
void Build(int l,int r,SgTree *Node)
{
	Node->L=l;Node->R=r;
	if(l==r)
	{
		Node->L_R=M[l];
		Node->iL_iR=Node->L_iR=Node->iL_R=0;
		Node->val=Node->L_R;
		Node->Left=Node->Right=ConstNode;
	}
	else
	{
		Node->Left=new SgTree;
		Node->Right=new SgTree;
		Build(l,(l+r)/2,Node->Left);
		Build((l+r)/2+1,r,Node->Right);
		Node->L_R=max(max(Node->Left->L_iR+Node->Right->iL_R,Node->Left->L_R+Node->Right->iL_R),max(Node->Left->L_iR+Node->Right->L_R,Node->Left->L_iR+Node->Right->iL_R));
		Node->L_iR=max(max(Node->Left->L_iR+Node->Right->iL_iR,Node->Left->L_R+Node->Right->iL_iR),max(Node->Left->L_iR+Node->Right->L_iR,Node->Left->L_iR+Node->Right->iL_iR));
		Node->iL_R=max(max(Node->Left->iL_iR+Node->Right->iL_R,Node->Left->iL_R+Node->Right->iL_R),max(Node->Left->iL_iR+Node->Right->L_R,Node->Left->iL_iR+Node->Right->iL_R));
		Node->iL_iR=max(max(Node->Left->iL_iR+Node->Right->iL_iR,Node->Left->iL_R+Node->Right->iL_iR),max(Node->Left->iL_iR+Node->Right->L_iR,Node->Left->iL_iR+Node->Right->iL_iR));
		Node->val=max(max(Node->L_R,Node->L_iR),max(Node->iL_R,Node->iL_iR));
	}
}
inline void Change(int pos,int num,SgTree *Node)
{
	
	if(pos==Node->L&&pos==Node->R)
		Node->val=Node->L_R=num;
	else
	{
		int Mid=(Node->L+Node->R)/2;
		if(pos<=Mid)
			Change(pos,num,Node->Left);
		if(pos>Mid)
			Change(pos,num,Node->Right);
		Node->L_R=max(max(Node->Left->L_iR+Node->Right->iL_R,Node->Left->L_R+Node->Right->iL_R),max(Node->Left->L_iR+Node->Right->L_R,Node->Left->L_iR+Node->Right->iL_R));
		Node->L_iR=max(max(Node->Left->L_iR+Node->Right->iL_iR,Node->Left->L_R+Node->Right->iL_iR),max(Node->Left->L_iR+Node->Right->L_iR,Node->Left->L_iR+Node->Right->iL_iR));
		Node->iL_R=max(max(Node->Left->iL_iR+Node->Right->iL_R,Node->Left->iL_R+Node->Right->iL_R),max(Node->Left->iL_iR+Node->Right->L_R,Node->Left->iL_iR+Node->Right->iL_R));
		Node->iL_iR=max(max(Node->Left->iL_iR+Node->Right->iL_iR,Node->Left->iL_R+Node->Right->iL_iR),max(Node->Left->iL_iR+Node->Right->L_iR,Node->Left->iL_iR+Node->Right->iL_iR));
		Node->val=max(max(Node->L_R,Node->L_iR),max(Node->iL_R,Node->iL_iR));
	}
}