记录编号	159721	评测结果	AAAAAAAAAA
题目名称	马拉松	最终得分	100
用户昵称	Dijkstra	是否通过	通过
代码语言	C++	运行时间	1.925 s
提交时间	2015-04-22 14:14:40	内存使用	5.43 MiB

#include<fstream>
#include<cmath>
#include<cstring>
#define MAXN 100001
#define INF 0x7fffffff
#define tree 1,N,1
#define left l,m,2*p
#define right m+1,r,2*p+1
#define Lc t[2*p]
#define Rc t[2*p+1]
#define P t[p]
using namespace std;
ifstream fin("marathona.in");
ofstream fout("marathona.out");
struct point{int x,y;};
struct leaf
{
	int s,m;
	int l;
}t[4*MAXN];
int N,Q,a,b,c,ans,sum;
point n[MAXN];
int d[MAXN];
int dis(point a,point b){return abs(a.x-b.x)+abs(a.y-b.y);}
void UPDATE(int p,int m)
{
	if(P.l==1) return;
	P.s=Lc.s+Rc.s;
	P.m=max(Lc.m,Rc.m);P.m=max(P.m,d[m]+d[m+1]-dis(n[m],n[m+2]));
	P.l=Lc.l+Rc.l;
}
void BUILD(int l,int r,int p)
{
	int m=(l+r)>>1;
	if(l==r)
	{
		P.s=d[l];
		P.m=0;
		P.l=1;
		return;
	}
	BUILD(left);BUILD(right);
	UPDATE(p,m);
}
int SUM(int l,int r,int p)
{
	int m=(l+r)>>1;
	if(l>=a&&r<=b) return P.s;
	int as=0;
	if(a<=m) as+=SUM(left);
	if(b>m) as+=SUM(right);
	return as;
}
void SET(int l,int r,int p)
{
	int m=(l+r)>>1;
	if(l==r)
	{
	    P.s=d[l];
		P.m=0;
		return;
	}
	if(c<=m) SET(left);
	if(c>m) SET(right);
	UPDATE(p,m);
}
void FIND(int l,int r,int p)
{
	int m=(l+r)>>1;
	if(l>=a&&r<=b)
	{
		ans=min(ans,sum-P.m);
		if(l!=a) ans=min(ans,sum-(d[l-1]+d[l]-dis(n[l-1],n[l+1])));
		if(r!=b) ans=min(ans,sum-(d[r]+d[r+1]-dis(n[r],n[r+2])));
		return;
	}
	if(a<=m) FIND(left);
	if(b>m) FIND(right);
}
int main()
{
	fin>>N>>Q;
	char ch;
	for(int i=1;i<=N;i++) fin>>n[i].x>>n[i].y;
	for(int i=1;i<N;i++) d[i]=dis(n[i],n[i+1]);
	N--;
	BUILD(tree);
	for(int i=1;i<=Q;i++)
	{
		fin>>ch;
		if(ch=='U')
		{
			fin>>c>>a>>b;
			n[c].x=a;n[c].y=b;
			if(c!=1) d[c-1]=dis(n[c-1],n[c]);
			if(c!=N+1) d[c]=dis(n[c],n[c+1]);
			SET(tree);c--;SET(tree);
		}
		else
		{
			ans=INF;
			fin>>a>>b;
			b--;
			sum=SUM(tree);
			FIND(tree);
			fout<<ans<<endl;
		}
	}
	return 0;
}