记录编号	437605	评测结果	AAAAAAAAAA
题目名称	马拉松	最终得分	100
用户昵称	Fisher.	是否通过	通过
代码语言	C++	运行时间	0.812 s
提交时间	2017-08-14 12:17:19	内存使用	4.89 MiB

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
/*
	区间维护路径和，和跳过某节点能省的最大距离。
	建树时维护某点到下一点的距离，以及跳过下一个点直接到第三个点能省的距离；
	注意开闭区间； 
	考虑好修改操作;需修改三个点；直接对原数据进行修改，然后更新线段树的点；
	 
*/
inline int read(){
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
	return x*f;
}
const int maxn=100010;
int n,m;
struct point{
	int x,y;
	int w,sheng;
}p[maxn];
int sum[4*maxn];
int msheng[4*maxn];
inline int dis(int x1,int y1,int x2,int y2){return abs(x1-x2)+abs(y1-y2);}
inline void pdis(int pos){
	if(pos+1<=n)p[pos].w=dis(p[pos].x,p[pos].y,p[pos+1].x,p[pos+1].y);
}
inline void psheng(int pos){
	if(pos+2<=n)p[pos].sheng=p[pos].w+p[pos+1].w-dis(p[pos].x,p[pos].y,p[pos+2].x,p[pos+2].y);
}
inline void build(int o,int l,int r){
	if(l==r){
		if(l+1<=n){
			sum[o]=p[l].w;
		}
		if(l+2<=n){
			msheng[o]=p[l].sheng;
		}
		return ;
	}
	int m=(l+r)>>1,ls=o<<1,rs=ls|1;
	build(ls,l,m);
	build(rs,m+1,r);
	sum[o]=sum[ls]+sum[rs];
	msheng[o]=max(msheng[ls],msheng[rs]);
}
inline void updata(int o,int l,int r,int nl,int nr){
	if(l>=nl&&r<=nr){
		if(l+1<=n){
			sum[o]=p[l].w;
		}
		if(l+2<=n){
			msheng[o]=p[l].sheng;
		}
		return ;
	}
	int m=(l+r)>>1,ls=o<<1,rs=ls|1;
	if(m>=nl)updata(ls,l,m,nl,nr);
	if(m<nr)updata(rs,m+1,r,nl,nr);
	sum[o]=sum[ls]+sum[rs];
	msheng[o]=max(msheng[ls],msheng[rs]);
}
inline int findsum(int o,int l,int r,int nl,int nr){
	if(l>=nl&&r<=nr)return sum[o]; 
	int ans=0;
	int m=(l+r)>>1,ls=o<<1,rs=ls|1;
	if(m>=nl)ans+=findsum(ls,l,m,nl,nr);
	if(m<nr)ans+=findsum(rs,m+1,r,nl,nr);
	return ans;
}
inline int findmax(int o,int l,int r,int nl,int nr){
	if(l>=nl&&r<=nr)return msheng[o];
	int ans=-0x7fffffff;
	int m=(l+r)>>1,ls=o<<1,rs=ls|1;
	if(m>=nl)ans=max(ans,findmax(ls,l,m,nl,nr));
	if(m<nr)ans=max(ans,findmax(rs,m+1,r,nl,nr));
	return ans;
}
int main(){
	freopen("marathona.in","r",stdin);
	freopen("marathona.out","w",stdout);
	n=read();m=read();
	for(int i=1;i<=n;i++){
		p[i].x=read();p[i].y=read();
	}
	for(int i=1;i<n;i++){
		pdis(i);
	}
	for(int i=1;i<=n-2;i++){
		psheng(i);
	}
	build(1,1,n-1);
	for(int i=1;i<=m;i++){
		char c;
		scanf("%s",&c);
		if(c=='U'){
			int pos=read(),xx=read(),yy=read();
			p[pos].x=xx;p[pos].y=yy;
			pdis(pos);psheng(pos);updata(1,1,n-1,pos,pos);
			if(pos-1>=1){pdis(pos-1);psheng(pos-1);updata(1,1,n-1,pos-1,pos-1);}
			if(pos-2>=1){psheng(pos-2);updata(1,1,n-1,pos-2,pos-2);}
		}
		if(c=='Q'){
			int l=read(),r=read();
			int ans=findsum(1,1,n-1,l,r-1)-findmax(1,1,n-1,l,r-2);//考虑好开闭区间 
			printf("%d\n",ans); 
		}
	}
	return 0;
}