记录编号	436222	评测结果	AAAAAAAAAA
题目名称	马拉松	最终得分	100
用户昵称	JustWB	是否通过	通过
代码语言	C++	运行时间	1.308 s
提交时间	2017-08-11 13:03:48	内存使用	1.07 MiB

#include<cstdio>
#include<cctype>
#include<algorithm>
#define mid_a ((l+r)>>1)
#define mid_b ((now->l+now->r)>>1)
const int maxn=1e5+5;
using namespace std;
struct stree
{
	int l,r,mx;
	stree *ls,*rs;
	stree(){l=r=mx=0;ls=rs=NULL;}
}*root;
inline int get();
stree *build(int l,int r);
stree *build_b(int l,int r);
int search(stree *now,int l,int r,bool j);
void change(stree *now,int pos,bool j);
int n,q;
int x[maxn],y[maxn];
int I,J;
stree *node;
int main()
{
	freopen("marathona.in","r",stdin);
	freopen("marathona.out","w",stdout);
	n=get();q=get();
	for(int i=1;i<=n;i++)x[i]=get(),y[i]=get();
	root=build(1,n-1);
	node=build_b(2,n-1);
	for(int i=1;i<=q;i++)
	{
		register char temp=getchar();
		if(temp=='Q')
		{
			I=get();J=get();
			printf("%d\n",search(root,I,J-1,0)-search(node,I+1,J-1,1));
		}
		else
		{
			I=get();
			x[I]=get();y[I]=get();
			if(I!=n)change(root,I,0);
			if(I!=1)change(root,I-1,0);
			if(I!=n)change(node,I,1);
			if(I!=1)change(node,I-1,1);
			if(I!=n-1)change(node,I+1,1);
		}
	}
	return 0;
}
void change(stree *now,int pos,bool j)
{
	if(now->l==now->r)
	{
		if(j)
		{
			int a=abs(x[pos]-x[pos-1])+abs(y[pos]-y[pos-1]);
			int b=abs(x[pos]-x[pos+1])+abs(y[pos]-y[pos+1]);
			int c=abs(x[pos-1]-x[pos+1])+abs(y[pos-1]-y[pos+1]);
			now->mx=-(c-a-b);
		}
		else now->mx=abs(x[pos]-x[pos+1])+abs(y[pos]-y[pos+1]);
	}
	else if(pos<=mid_b)
	{
		change(now->ls,pos,j);
		if(j)now->mx=max(now->ls->mx,now->rs->mx);
		else now->mx=now->ls->mx+now->rs->mx;
	}
	else
	{
		change(now->rs,pos,j);
		if(j)now->mx=max(now->ls->mx,now->rs->mx);
		else now->mx=now->ls->mx+now->rs->mx;
	}
}
int search(stree *now,int l,int r,bool j)
{
	if(now->l==l&&now->r==r)return now->mx;
	else if(r<=mid_b)return search(now->ls,l,r,j);
	else if(l>mid_b)return search(now->rs,l,r,j);
	else if(j)return max(search(now->ls,l,mid_b,j),search(now->rs,mid_b+1,r,j));
	else return search(now->ls,l,mid_b,j)+search(now->rs,mid_b+1,r,j);
}
stree *build_b(int l,int r)
{
	stree *p=new stree();
	p->l=l;p->r=r;
	if(l==r)
	{
		int a=abs(x[l]-x[l-1])+abs(y[l]-y[l-1]);
		int b=abs(x[l]-x[l+1])+abs(y[l]-y[l+1]);
		int c=abs(x[l-1]-x[l+1])+abs(y[l-1]-y[l+1]);
		p->mx=-(c-a-b);
	}
	else
	{
		p->ls=build_b(l,mid_a);
		p->rs=build_b(mid_a+1,r);
		p->mx=max(p->ls->mx,p->rs->mx);
	}
	return p;
}
stree *build(int l,int r)
{
	stree *p=new stree();
	p->l=l;p->r=r;
	if(l==r)p->mx=abs(x[l]-x[l+1])+abs(y[l]-y[l+1]);
	else 
	{
		p->ls=build(l,mid_a);
		p->rs=build(mid_a+1,r);
		p->mx=p->ls->mx+p->rs->mx;
	}
	return p;
}
inline int get()
{
	int t=0,j=1;char c=getchar();
	while(!isdigit(c))
	{
		if(c=='-')j=-1;
		c=getchar();
	}
	while(isdigit(c))
	{
		t=(t<<3)+(t<<1)+c-'0';
		c=getchar();
	}
	return j*t;
}