记录编号	159629	评测结果	AAAAAAAAAA
题目名称	马拉松	最终得分	100
用户昵称	Chenyao2333	是否通过	通过
代码语言	C++	运行时间	1.345 s
提交时间	2015-04-22 12:09:26	内存使用	8.78 MiB

#include<cstdio>
#include<algorithm>
using namespace std;
const int L_N=1e5+10;
const int INF=1e9+10;
struct TreeArr{
	int a[L_N];
	int lowbit(int i){ return i&-i; }
	void add(int p,int val){
		for(;p<L_N;p+=lowbit(p)){
			a[p]+=val;
		}
	}
	int query(int p){
		int ret=0;
		for(;p;p-=lowbit(p)){
			ret+=a[p];
		}
		return ret;
	}
	int query(int l,int r){
		return query(r)-query(l-1);
	}
}ta;

int N,M,X[L_N],Y[L_N];
int pro[L_N];

int calc_len(int i,int j){
	return abs(X[i]-X[j])+abs(Y[i]-Y[j]);
}
int calc_profit(int i){
	if(i==1 || i==N) return 0;
	return max(calc_len(i-1,i) + calc_len(i,i+1) - calc_len(i-1,i+1),0);
}

struct node{
	int ls,rs,l,r;
	int val,mx;
}t[L_N*4];
int node_cnt;
void push_up(int x){
	t[x].mx=t[x].val;
	if(t[x].ls) t[x].mx=max(t[x].mx,t[t[x].ls].mx);
	if(t[x].rs) t[x].mx=max(t[x].mx,t[t[x].rs].mx);
}
void build(int x,int l,int r){
	t[x].l=l, t[x].r=r;
	if(l==r){
		t[x].val=pro[l];
		push_up(x);
		return ;
	}
	int mid=(l+r)/2;
	t[x].ls=++node_cnt, t[x].rs=++node_cnt;
	build(t[x].ls,l,mid);
	build(t[x].rs,mid+1,r);
	push_up(x);
}
void change(int x,int p,int val){
	if(t[x].l==t[x].r){
		t[x].val=val;
		push_up(x);
		return;
	}
	int mid=(t[x].l+t[x].r)/2;
	if(p<=mid) change(t[x].ls,p,val);
	else change(t[x].rs,p,val);
	push_up(x);
}
int query(int x,int l,int r){
	if(l<=t[x].l && t[x].r<=r){
		return t[x].mx;
	}
	int ret=0,mid=(t[x].l+t[x].r)/2;
	if(l<=mid) ret=max(ret,query(t[x].ls,l,r));
	if(r>=mid+1) ret=max(ret,query(t[x].rs,l,r));
	return ret;
}



int main(){
	freopen("marathona.in","r",stdin);
	freopen("marathona.out","w",stdout);
	scanf("%d %d",&N,&M);
	for(int i=1;i<=N;i++){
		scanf("%d %d",X+i,Y+i);
	}
	for(int i=2;i<N;i++){
		pro[i]=calc_profit(i);
	}
	for(int i=1;i<N;i++){
		ta.add(i,calc_len(i,i+1));
	}
	build(++node_cnt,1,N);
	
	for(int i=1;i<=M;i++){
		char op[2]; scanf("%s",op);
		if(op[0]=='Q'){
			int l,r; scanf("%d %d",&l,&r);
			int ans=ta.query(l,r-1);
			if(l+1<=r-1) ans-=query(1,l+1,r-1);
			printf("%d\n",ans);
		}else{
			int id,x,y; scanf("%d %d %d",&id,&x,&y);
			int l1=calc_len(id-1,id), l2=calc_len(id,id+1);
			X[id]=x, Y[id]=y;
			if(id>1) ta.add(id-1,calc_len(id-1,id)-l1);
			if(id<N) ta.add(id,calc_len(id,id+1)-l2);
			
			change(1,id,calc_profit(id));
			if(id>1) change(1,id-1,calc_profit(id-1));
			if(id<N) change(1,id+1,calc_profit(id+1));
		}
	}
	
	return 0;
}