记录编号	159731	评测结果	AAAAAAAAAA
题目名称	马拉松	最终得分	100
用户昵称	ggwdwsbs	是否通过	通过
代码语言	C++	运行时间	1.327 s
提交时间	2015-04-22 15:24:16	内存使用	72.77 MiB

#include<stdio.h>
#include<cstring>
const int maxn=1000010;
const int INF=2147483600;
struct tree
{
	int left,right,sum,max;
}a[maxn*4];
int b[maxn];
int ret;
int max(int x,int y)
{
	if(x>y) return x;
	else return y;
}
int x[maxn];
int y[maxn];
int n,q,l,r,x1,y1,j;
char c;
int abs(int x)
{
	if(x>0) return x;
	else return -x;
}
int dis(int i,int j)
{
	return abs(x[i]-x[j]) + abs(y[i]-y[j]);
}
int build(int k,int l,int r)
{
	a[k].left=l;
	a[k].right=r;
	if(l==r)
	{
		a[k].sum=b[l];
		if(l>1&&l<n) a[k].max=b[l]+b[l+1]-dis(l-1,l+1);
		else a[k].max=-INF;
	} 
	else
	{
		build(2*k,l,(l+r)/2);
		build(2*k+1,(l+r)/2+1,r);
		a[k].sum=a[2*k].sum+a[2*k+1].sum;
		a[k].max=max(a[2*k].max,a[2*k+1].max);
	}
}
int change_sum(int k,int x,int num)
{
	if(a[k].left==a[k].right) a[k].sum=num;
	else
	{
		if(x<=(a[k].left+a[k].right)/2) change_sum(2*k,x,num);
		if(x>(a[k].left+a[k].right)/2) change_sum(2*k+1,x,num);
		a[k].sum=a[2*k].sum+a[2*k+1].sum;
	}	
}
int change_max(int k,int x,int num)
{
	if(a[k].left==a[k].right) a[k].max=num;
	else
	{
		if(x<=(a[k].left+a[k].right)/2) change_max(2*k,x,num);
		if(x>(a[k].left+a[k].right)/2) change_max(2*k+1,x,num);
		a[k].max=max(a[2*k].max,a[2*k+1].max);
	}	
}
int query(int k,int l,int r)
{
	if(l>a[k].right||r<a[k].left) return 0;
	if(l<=a[k].left&&a[k].right<=r)
	{
		ret=max(ret,a[k].max);
		return a[k].sum;
	} 
	else return query(2*k,l,r)+query(2*k+1,l,r);
}
int main()
{
	freopen("marathona.in","r",stdin);
	freopen("marathona.out","w",stdout);
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&x[i],&y[i]);
		b[i]=dis(i,i-1);
	}
	b[1]=0;
	build(1,1,n);
	for(int i=1;i<=q;i++)
	{
		c=getchar();
		while(c!='Q'&&c!='U') 
		 c=getchar();
		if(c=='Q')
		{
			scanf("%d%d",&l,&r);
			int ans=query(1,l+1,r);
			ret=-INF;
			query(1,l+1,r-1);
			ans-=ret;
			printf("%d\n",ans); 
		}
		if(c=='U')
		{
			scanf("%d%d%d",&j,&x1,&y1);
			x[j]=x1;
			y[j]=y1;
			if(j!=1) b[j]=dis(j-1,j);
			if(j+1<=n) 
			{
				b[j+1]=dis(j+1,j);
				change_sum(1,j+1,b[j+1]);
			}
			change_sum(1,j,b[j]);
			if(j+1<=n&&j-1>=1) change_max(1,j,b[j]+b[j+1]-dis(j-1,j+1));
			if(j+2<=n) change_max(1,j+1,b[j+1]+b[j+2]-dis(j,j+2));
			if(j-2>=1) change_max(1,j-1,b[j-1]+b[j]-dis(j-2,j));
		}
	}
}