记录编号	335845	评测结果	AAAAAAAAAA
题目名称	马拉松	最终得分	100
用户昵称	LOSER	是否通过	通过
代码语言	C++	运行时间	2.678 s
提交时间	2016-11-02 19:30:46	内存使用	7.18 MiB

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define maxn 100010
int n,m;
struct Point{int x,y;}a[maxn];
int Getdis(int x,int y){return abs(a[x].x-a[y].x)+abs(a[x].y-a[y].y);}
struct Segment_tree{
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
#define mid ((l+r)>>1)
	int Max[maxn<<2],sum[maxn<<2];
	void Modify(int rt,int l,int r) {Max[rt]=max(Max[rt<<1],Max[rt<<1|1]);sum[rt]=sum[rt<<1]+sum[rt<<1|1];}
	void Build(int rt,int l,int r){
		if(l==r) {
			Max[rt]=Getdis(l-1,l)+Getdis(l,l+1)-Getdis(l-1,l+1);
			sum[rt]=Getdis(l-1,l);
			return;
		}	Build(lson); Build(rson);
		Modify(rt,l,r);
	}	
	int Querymax(int s,int t,int rt,int l,int r){
		if(s>t) return 0;
		if(s<=l && t>=r) return Max[rt];
		if(t<=mid) return Querymax(s,t,lson);
		if(s>mid) return Querymax(s,t,rson);
		return max(Querymax(s,t,lson),Querymax(s,t,rson));
	}
	int Querysum(int s,int t,int rt,int l,int r){
		if(s>t) return 0;
		if(s<=l && t>=r) return sum[rt];
		if(t<=mid) return Querysum(s,t,lson);
		if(s>mid) return Querysum(s,t,rson);
		return Querysum(s,t,lson)+Querysum(s,t,rson);	
	}
	void Insert(int x,int rt,int l,int r) {
		if(l==r) {
			Max[rt]=Getdis(l-1,l)+Getdis(l,l+1)-Getdis(l-1,l+1);
			sum[rt]=Getdis(l-1,l);
			return;	
		}	
		if(x<=mid) Insert(x,lson); 
		else Insert(x,rson); 
		Modify(rt,l,r);
	}
}T1,T2;
int main(){
	freopen("marathona.in","r",stdin); freopen("marathona.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;i++) scanf("%d%d",&a[i].x,&a[i].y);
	//为了让下标容易处理，所以从0开始 
	n-=2; T1.Build(1,1,n);  T2.Build(1,1,n+1);
	while( m-- ) {
	//	printf("--------DONE-------\n");
		char ch; scanf(" %c",&ch);
		if(ch=='U') {
			int pos,x,y; scanf("%d%d%d",&pos,&x,&y); pos--;
			a[pos].x=x,a[pos].y=y; 
			if(pos!=0 && pos!=n+1)T1.Insert(pos,1,1,n);			
			if(pos+1!=0 && pos!=n)T1.Insert(pos+1,1,1,n);
			if(pos-1!=0 && pos-1!=n+1)T1.Insert(pos-1,1,1,n);
			//维护线段树 
			if(pos!=0){
				T2.Insert(pos,1,1,n+1);
				T2.Insert(pos+1,1,1,n+1);
			}
			if(pos==0)T2.Insert(pos+1,1,1,n+1);
			//printf("%d\n",T2.Getsum(1));
			/*for(int i=1;i<=n+1;i++) {
				printf("<%d>\n",T2.Getsum(i));	
			}*/
		}		
		if(ch=='Q') {
			int s,t,temp; scanf("%d%d",&s,&t); t--,s--;
			//因为Getsum(0)会死循环 
			temp=T2.Querysum(s+1,t,1,1,n+1)-T1.Querymax(s+1,t-1,1,1,n);	
			printf("%d\n",temp);
		}
	}
	getchar(); getchar();
	return 0;
}
/*
5 10
2 5
1 3
1 1
3 5
2 2
U 2 3 2
Q 2 4
*/