记录编号	162864	评测结果	AAAAAAAAAA
题目名称	马拉松	最终得分	100
用户昵称	stdafx.h	是否通过	通过
代码语言	C++	运行时间	0.720 s
提交时间	2015-05-21 05:54:32	内存使用	15.55 MiB

#define lson l,m,t
#define rson m+1,r,t|1

#include <cstdio>

using namespace std;

struct ANYTHING{
	int id,mx,data;
};

struct EVR{
	int x,y;
};

ANYTHING tree[1000000];//代表和后面相连的值
EVR MAP[500001];

inline int ABS(int);
inline int MAX(int,int);
inline int in();

void BUILD(int,int,int);
void UPDATE(int,int,int,int);
ANYTHING QUERY(int,int,int,int,int);

int n,q,a,b,c,CUR_ID;
ANYTHING ANS;

int main()
{
	freopen("marathona.in","r",stdin);
	freopen("marathona.out","w",stdout);
	n=in();q=in();
	for(int i=1;i<=n;i++){
		MAP[i].x=in();
		MAP[i].y=in();
	}
	BUILD(1,n,1);
	for(int i=1;i<=q;i++){
		char inp=getchar();
		while(inp!='Q'&&inp!='U'){
			inp=getchar();
		}
		if(inp=='Q'){
			a=in();b=in();
			if(b-a<=1){
				printf("%d\n",ABS(MAP[b].x-MAP[a].x)+ABS(MAP[b].y-MAP[a].y));
			}
			else{
				ANS=QUERY(a,b-2,1,n,1);
				printf("%d\n",ABS(MAP[b].x-MAP[b-1].x)+ABS(MAP[b].y-MAP[b-1].y)+ANS.data-ANS.mx);
			}
		}
		else{
			a=in();b=in();c=in();
			MAP[a].x=b;MAP[a].y=c;
			UPDATE(a,1,n,1);
			/*
			if(a>1){
				UPDATE(a-1,1,n,1);
			}
			if(a>2){
				UPDATE(a-2,1,n,1);
			}*/
		}
	}
	return 0;
}
inline int ABS(int temp)
{return temp>0? temp:(-temp);}

inline int MAX(int a,int b)
{return a>b? a:b;}

inline int in()
{
	char c=getchar();int x=0;bool flag=0;
	while(c<'0'||c>'9'){
		if(c=='-'){
			flag=1;
		}
		c=getchar();
	}

    for(;c>='0'&&c<='9';c=getchar())
		x=x*10+c-48;
	if(flag) return -x;
    return x;
}

void BUILD(int l,int r,int rt)
{
    if(l==r){
		CUR_ID++;
		tree[rt].id=CUR_ID;
        tree[rt].data=ABS(MAP[tree[rt].id].x-MAP[tree[rt].id+1].x)+ABS(MAP[tree[rt].id].y-MAP[tree[rt].id+1].y);
        if(tree[rt].id<=n-2)
        	tree[rt].mx=tree[rt].data+ABS(MAP[tree[rt].id+1].x-MAP[tree[rt].id+2].x)+ABS(MAP[tree[rt].id+1].y-MAP[tree[rt].id+2].y)-ABS(MAP[tree[rt].id].x-MAP[tree[rt].id+2].x)-ABS(MAP[tree[rt].id].y-MAP[tree[rt].id+2].y);
        return;
    }
    int m=(l+r)>>1,t=rt<<1;
    BUILD(lson);
    BUILD(rson);
    tree[rt].mx=MAX(tree[t].mx,tree[t|1].mx);
    tree[rt].data=tree[t].data+tree[t|1].data;
    return;
}

void UPDATE(int pos,int l,int r,int rt)
{
    if(l==r){
        tree[rt].data=ABS(MAP[tree[rt].id].x-MAP[tree[rt].id+1].x)+ABS(MAP[tree[rt].id].y-MAP[tree[rt].id+1].y);
        if(tree[rt].id<=n-2)
        	tree[rt].mx=tree[rt].data+ABS(MAP[tree[rt].id+1].x-MAP[tree[rt].id+2].x)+ABS(MAP[tree[rt].id+1].y-MAP[tree[rt].id+2].y)-ABS(MAP[tree[rt].id].x-MAP[tree[rt].id+2].x)-ABS(MAP[tree[rt].id].y-MAP[tree[rt].id+2].y);
        return;
    }
    int m=(l+r)>>1,t=rt<<1;
    if((pos-1<=m&&pos>1)||(pos-2<=m&&pos>2)||(pos<=m)){
        UPDATE(pos,lson);
    }
    if(pos>m){
		UPDATE(pos,rson);
    }
    tree[rt].mx=MAX(tree[t].mx,tree[t|1].mx);
    tree[rt].data=tree[t].data+tree[t|1].data;
    return;
}

ANYTHING QUERY(int pos_l,int pos_r,int l,int r,int rt)
{
    if(pos_l<=l&&r<=pos_r){
        return tree[rt];
    }
    int m=(l+r)>>1,t=rt<<1;
    ANYTHING a,b;
    a.mx=b.mx=0;
	a.data=b.data=0;
    if(pos_l<=m){
        a=QUERY(pos_l,pos_r,lson);
    }
    if(pos_r>m){
        b=QUERY(pos_l,pos_r,rson);
    }
    a.mx=MAX(a.mx,b.mx);
    a.data+=b.data;
    return a;
}