记录编号	159682	评测结果	AAAAAAAAAA
题目名称	马拉松	最终得分	100
用户昵称	真呆菌	是否通过	通过
代码语言	C++	运行时间	1.289 s
提交时间	2015-04-22 13:50:57	内存使用	6.34 MiB

#include<cstdio>
using namespace std;
typedef long long LL;
const int N = 100100;
int n,m,M;
int px[N],py[N],f[N],g[N];
LL T1[N<<2],T2[N<<2];

LL Max(LL x,LL y){if(x>y) return x;return y;}
int Abs(int x){if(x<0) return -x;return x;}
int Calc(int x1,int y1,int x2,int y2){return Abs(x1-x2)+Abs(y1-y2);}
int PCalc(int x,int y){return Calc(px[x],py[x],px[y],py[y]);}

void Change1(int x,LL y){
	x+=M;T1[x]=y;
	for(x>>=1;x;x>>=1) T1[x]=T1[x<<1]+T1[x<<1|1];
	return;
}

void Change2(int x,LL y){
	x+=M;T2[x]=y;
	for(x>>=1;x;x>>=1) T2[x]=Max(T2[x<<1],T2[x<<1|1]);
	return;
}

LL Query1(int x,int y){
	if(x>y) return 0ll;
	LL res=0ll;
	for(x=x+M-1,y=y+M+1;x^y^1;x>>=1,y>>=1){
		if(~x&1) res+=T1[x^1];
		if( y&1) res+=T1[y^1];
	}
	return res;
}

LL Query2(int x,int y){
	if(x>y) return 0ll;
	LL res=0ll;
	for(x=x+M-1,y=y+M+1;x^y^1;x>>=1,y>>=1){
		if(~x&1) res=Max(res,T2[x^1]);
		if( y&1) res=Max(res,T2[y^1]);
	}
	return res;
}

int main(){
	#define READ
	#ifdef READ
	    freopen("marathona.in","r",stdin);
	    freopen("marathona.out","w",stdout);
	#endif
	scanf("%d%d",&n,&m);
	for(M=1;M<=n+2;M<<=1);
	for(int i=1;i<=n;i++)
		scanf("%d%d",&px[i],&py[i]);
	f[1]=PCalc(1,2);
	for(int i=2;i<n;i++)
	   g[i]=PCalc(i-1,i)+PCalc(i,i+1)-PCalc(i-1,i+1),
	   f[i]=PCalc(i,i+1);
	for(int i=1;i<n;i++) T1[i+M]=f[i];
	for(int i=M-1;i;i--) T1[i]=T1[i<<1]+T1[i<<1|1];
	for(int i=2;i<n;i++) T2[i+M]=g[i];
	for(int i=M-1;i;i--) T2[i]=Max(T2[i<<1],T2[i<<1|1]);
	char typ[10];int x,y,z;
	for(int i=1;i<=m;i++){
		scanf("%s",typ);
		if(typ[0]=='Q'){
			scanf("%d%d",&x,&y);
			printf("%lld\n",Query1(x,y-1)-Query2(x+1,y-1));
		}
		else{
			scanf("%d%d%d",&z,&x,&y);
			px[z]=x;py[z]=y;
			for(int j=z-1;j<=z;j++){
				if(j>=1&&j<n){
					f[j]=PCalc(j,j+1);
					Change1(j,f[j]);
				}
			}
			for(int j=z-1;j<=z+1;j++){
				if(j>1&&j<n){
					g[j]=PCalc(j-1,j)+PCalc(j,j+1)-PCalc(j-1,j+1);
					Change2(j,g[j]);
				}
			}
		}
	}
	//while(1);
	return 0;
}