记录编号	90675	评测结果	AAAAAAAAAAA
题目名称	最优挤奶法	最终得分	100
用户昵称	digital-T	是否通过	通过
代码语言	C++	运行时间	0.346 s
提交时间	2014-03-08 17:46:13	内存使用	5.02 MiB

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int N,D,M[40010],tot=0;
struct seg
{
	int l,r,Lchild,Rchild;
	long long sum,sum_no_left,sum_no_right,sum_no_sides;
}tree[100010];
inline long long max(long long a,long long b,long long c,long long d){return max(max(a,b),max(c,d));}
void update(int root)
{
	seg &now=tree[root];
	if(now.l==now.r)
	{
		now.sum=M[now.l];
		now.sum_no_left=0;
		now.sum_no_right=0;
		now.sum_no_sides=0;
	}
	else
	{
		seg &LSON=tree[now.Lchild],&RSON=tree[now.Rchild];		
		now.sum_no_sides=max( LSON.sum_no_left + RSON.sum_no_sides , LSON.sum_no_sides + RSON.sum_no_right );
		now.sum_no_left=max( LSON.sum_no_left + RSON.sum_no_left , LSON.sum_no_sides + RSON.sum );
		now.sum_no_right=max( LSON.sum_no_right + RSON.sum_no_right , LSON.sum + RSON.sum_no_sides );
		now.sum=max(LSON.sum_no_right + RSON.sum , LSON.sum + RSON.sum_no_left);
	}
}
void Build(int root,int l,int r)
{
	tree[root].l=l;
	tree[root].r=r;
	if(l!=r)
	{
		int m=(l+r)/2;
		tree[root].Lchild=++tot;
		Build(tot,l,m);
		tree[root].Rchild=++tot;
		Build(tot,m+1,r);
	}
	else
	{
		tree[root].Lchild=tree[root].Rchild=-1;
	}
	update(root);
}
void change(int root,int k)
{
	if(tree[root].Lchild!=-1)
	{
		if( k <= (tree[root].l+tree[root].r)/2 )
			change(tree[root].Lchild,k);
		else
			change(tree[root].Rchild,k);
	}
	update(root);
}
int main()
{
	freopen("optmilk.in","r",stdin);
	freopen("optmilk.out","w",stdout);
	scanf("%d%d",&N,&D);
	for(int i=1;i<=N;i++)
	{
		scanf("%d",&M[i]);
	}
	Build(0,1,N);
	int k,m;
	long long ans=0;
	for(int i=1;i<=D;i++)
	{
		scanf("%d%d",&k,&m);
		M[k]=m;
		change(0,k);
		ans+=tree[0].sum;
	}
	printf("%lld\n",ans);
	return 0;
}