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

#include <fstream>
#include <algorithm>
using namespace std;
ifstream in("marathona.in");
ofstream out("marathona.out");
int n,q;
int len[100001]={0},skip[100001]={0};
class nobe
{
public:
	int x;
	int y;
}po[100001];
class node
{
public:
	int l,r;
	node *lc,*rc;
	int sum,jump;
	node()
	{
		l=r=0;
		lc=rc=NULL;
		sum=jump=0;
	}
	void push()
	{
		if(lc!=NULL)
		{
			sum=lc->sum+rc->sum;
			jump=max(lc->jump,rc->jump);
		}
	}
	void mod(int x,bool type,int w)
	{
		if(l>x||r<x)return ;
		if(l==x&&r==x)
		{
			if(!type)sum=w;
			else jump=w;
		}
		else
		{
			lc->mod(x,type,w);
			rc->mod(x,type,w);
			push();
		}
	}
	int query(int a,int b,bool type)
	{
		if(l>b||r<a)return 0;
		if(l>=a&&r<=b)
		{
			if(!type)return sum;
			else return jump;
		}
		else
		{
			if(!type)return lc->query(a,b,type)+rc->query(a,b,type);
			else return max(lc->query(a,b,type),rc->query(a,b,type));
		}
		
	}
};
node* build(int a[],int b[],int x,int y)
{
	node *p=new node();
	p->l=x;
	p->r=y;
	if(x==y)
	{
		p->sum=a[x];
		p->jump=b[x];
	}
	else
	{
		int mid=(x+y)/2;
		p->lc=build(a,b,x,mid);
		p->rc=build(a,b,mid+1,y);
		p->push();
	}
	return p;
}
int dis2(nobe a,nobe b)
{
	int c=0;
	c=abs(a.x-b.x);
	c+=abs(a.y-b.y);
	return c;
}
node *root;
int main()
{
	int i,j,k,l,a,b,c,temp=0;
	int best=9999999;
	int ans=0;
	char d;
	in>>n>>q;
	//out<<n<<' '<<q<<endl;
	for(i=1;i<=n;i++)in>>po[i].x>>po[i].y;
	for(i=1;i<n;i++)len[i]=dis2(po[i],po[i+1]);
	for(i=2;i<n;i++)skip[i]=len[i-1]+len[i]-dis2(po[i-1],po[i+1]);
	root=build(len,skip,1,n);
	for(i=1;i<=q;i++)
	{
		in>>d;
		//out<<d<<' ';
		if(d=='Q')
		{
			//out<<"fuck"<<endl;
			in>>a>>b;
			//out<<ans<<endl;
			ans=root->query(a,b-1,0)-root->query(a+1,b-1,1);
			out<<ans<<endl;
		}
		else
		{
			in>>a;
			in>>po[a].x>>po[a].y;
			for(j=a-1;j<=a;j++)
			{
				if(j>=1&&j+1<=n)
				{
				len[j]=dis2(po[j],po[j+1]);
				root->mod(j,0,len[j]);
				}
			}
			for(j=a-1;j<=a+1;j++)
			{
				if(j-1>=1&&j+1<=n)
				{
					skip[j]=len[j-1]+len[j]-dis2(po[j-1],po[j+1]);
					root->mod(j,1,skip[j]);
				}
			}
		}
	}
	return 0;
}