记录编号	159667	评测结果	AAAAAAAAAA
题目名称	马拉松	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	1.643 s
提交时间	2015-04-22 13:20:33	内存使用	1.66 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iomanip>
#include<cstdlib>
using namespace std;
#define Nil NULL
const int SIZEN=100010;
//一个节点的"长度"是它后面那条边的长度
class Node{
public:
	int l,r;
	Node *lc,*rc;
	int sum,leap;//长度之和,最长跳跃距离
	Node(){
		l=r=0;
		lc=rc=Nil;
		sum=leap=0;
	}
	void push_up(void){
		if(lc!=Nil){
			sum=lc->sum+rc->sum;
			leap=max(lc->leap,rc->leap);
		}
	}
	//0是sum,1是leap
	void modify(int x,bool type,int w){
		if(l>x||r<x) return;
		if(l==x&&r==x){
			if(type==0) sum=w;
			else leap=w;
		}
		else{
			lc->modify(x,type,w);
			rc->modify(x,type,w);
			push_up();
		}
	}
	int query(int a,int b,bool type){
		if(l>b||r<a) return 0;
		if(l>=a&&r<=b){
			if(type==0) return sum;
			else return leap;
		}
		else{
			if(type==0) return lc->query(a,b,type)+rc->query(a,b,type);
			else return max(lc->query(a,b,type),rc->query(a,b,type));
		}
	}
};
Node* build(int a[],int b[],int x,int y){
	Node *p=new Node;
	p->l=x,p->r=y;
	if(x==y){
		p->sum=a[x];
		p->leap=b[x];
	}
	else{
		int mid=(x+y)/2;
		p->lc=build(a,b,x,mid);
		p->rc=build(a,b,mid+1,y);
		p->push_up();
	}
	return p;
}
class Point{
public:
	int x,y;
};
int mdis(const Point &a,const Point &b){
	return abs(a.x-b.x)+abs(a.y-b.y);
}
int N,Q;
Node *root;
Point P[SIZEN];
int len[SIZEN]={0},skip[SIZEN]={0};
void work(void){
	char cmd[10];
	int a,b;
	for(int i=1;i<=Q;i++){
		scanf("%s",cmd);
		if(cmd[0]=='Q'){//查询
			scanf("%d%d",&a,&b);
			printf("%d\n",root->query(a,b-1,0)-root->query(a+1,b-1,1));
		}
		else if(cmd[0]=='U'){//修改
			scanf("%d",&a);
			scanf("%d%d",&P[a].x,&P[a].y);
			for(int i=a-1;i<=a;i++){
				if(1<=i&&i+1<=N){
					len[i]=mdis(P[i],P[i+1]);
					root->modify(i,0,len[i]);
				}
			}
			for(int i=a-1;i<=a+1;i++){
				if(1<=i-1&&i+1<=N){
					skip[i]=len[i-1]+len[i]-mdis(P[i-1],P[i+1]);
					root->modify(i,1,skip[i]);
				}
			}
			
		}
	}
}
void read(void){
	scanf("%d%d",&N,&Q);
	for(int i=1;i<=N;i++) scanf("%d%d",&P[i].x,&P[i].y);
	for(int i=1;i<N;i++) len[i]=mdis(P[i],P[i+1]);
	for(int i=2;i<N;i++) skip[i]=len[i-1]+len[i]-mdis(P[i-1],P[i+1]);
}
int main(){
	freopen("marathona.in","r",stdin);
	freopen("marathona.out","w",stdout);
	read();
	root=build(len,skip,1,N);
	work();
	return 0;
}