记录编号	461837	评测结果	AAAAAAAAAA
题目名称	马拉松	最终得分	100
用户昵称	~玖湫~	是否通过	通过
代码语言	C++	运行时间	0.697 s
提交时间	2017-10-20 20:06:42	内存使用	5.29 MiB

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
const int M=100005;
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
typedef pair<int,int> dou;
int n,m;
int x[M],y[M],len[M];
int sum[M<<2],mlen[M<<2],llen[M<<2],rlen[M<<2];
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
inline int cal(int a,int b) {return abs(x[a]-x[b])+abs(y[a]-y[b]);}
inline void pushup(int rt,int l,int r){
	int mid=l+r>>1,ls=rt<<1,rs=rt<<1|1;
	sum[rt]=sum[ls]+sum[rs];
	llen[rt]=llen[ls];rlen[rt]=rlen[rs];
	mlen[rt]=max(mlen[ls],mlen[rs]);
	int use=rlen[ls]+llen[rs]-cal(mid,mid+2);
	mlen[rt]=max(mlen[rt],use);
}
inline void bt(int rt,int l,int r){
	if(l==r){
		llen[rt]=rlen[rt]=sum[rt]=len[l];
		mlen[rt]=0; return ;
	}int mid=l+r>>1;
	bt(lson);bt(rson);pushup(rt,l,r);
}
inline void change(int pos,int zhi,int rt,int l,int r){
	if(l==r){
		llen[rt]=rlen[rt]=sum[rt]=zhi;
		mlen[rt]=0; return ;
	}int mid=l+r>>1;
	if(pos<=mid) change(pos,zhi,lson);
	else change(pos,zhi,rson);
	pushup(rt,l,r);
}
inline dou query(int s,int t,int rt,int l,int r){
	if(s<=l&&r<=t) {return dou(sum[rt],mlen[rt]);}
	int mid=l+r>>1;int res=0,su=0,num=0;dou tmp;
	if(s<=mid){
		tmp=query(s,t,lson);su+=tmp.first;
		res=max(res,tmp.second);++num;
	}if(t>mid){
		tmp=query(s,t,rson);su+=tmp.first;
		res=max(res,tmp.second);++num;
	}if(num==2){
		res=max(res,len[mid]+len[mid+1]-cal(mid,mid+2));	
	}return dou(su,res);
}
int DK(){
	freopen("marathona.in","r",stdin);
	freopen("marathona.out","w",stdout);
	n=read();m=read();
	for(int i=1;i<=n;++i) x[i]=read(),y[i]=read();
	for(int i=1;i<n;++i) len[i]=cal(i,i+1);
	bt(1,1,n-1);char s[2];int xx,yy,zz;
	while(m--){
		scanf("%s",s);
		if(s[0]=='U'){
			zz=read();x[zz]=read();y[zz]=read();
			if(zz!=1) {len[zz-1]=cal(zz-1,zz);change(zz-1,len[zz-1],1,1,n-1);}
			if(zz!=n) {len[zz]=cal(zz,zz+1);change(zz,len[zz],1,1,n-1);}
			continue;
		}xx=read();yy=read();
		dou ans=query(xx,yy-1,1,1,n-1);
		printf("%d\n",ans.first-ans.second);
	}return 0;
}
int dk=DK();
int main(){;}