记录编号	159886	评测结果	AAAAAAAAAA
题目名称	马拉松	最终得分	100
用户昵称	wolf.	是否通过	通过
代码语言	C++	运行时间	2.013 s
提交时间	2015-04-22 22:19:49	内存使用	0.31 MiB

#include<iostream>
#include<fstream>
#include<bitset>
#include<vector>
#include<deque>
#include<map>
#include<set>
#include<queue>
#include<string>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<cstdio>
using namespace std;
#if defined wolf
const string ok="OK";
const string kk="	";
ofstream nnew("marathona.in",ios::app);
ifstream fin("marathona.in");
#define fout cout
#define Endl endl
#else
ifstream fin("marathona.in");
ofstream fout("marathona.out");
#endif
class node{
public:
	int x,y;
	node(){
	}
	node(int a,int b){
		x=a;
		y=b;
	}
};
class llink{
public:
	int l,r,di;
	llink(){
		di=999999999;
	}
};
vector<llink> TT;//线段树
vector<int> num;//树状数组
vector<node> PP;//原始数据
int calc(int x1,int y1,int x2,int y2){
	return abs(x1-x2)+abs(y1-y2);
}
////////////////////////////////////树状数组
int lowbit(int n){
	return n&(-n);
}
void _add(int p,int n){
	for(int i=p;i<num.size();i+=lowbit(i)){
		num[i]+=n;
	}
}
long long _sum(int n){
	long long ans=0;
	for(int i=n;i>0;i-=lowbit(i)){
		ans+=num[i];
	}
	return ans;
}
int sum(int a,int b){
	if(a>b){
		swap(a,b);
	}
	long long ans=0;
	ans=_sum(b);
	ans-=_sum(a);
	return ans;
}
void rewrite_len(int p,int x,int y){
	int older,newer;
	if(p!=0){//不是左顶点
		older=sum(p-1,p);
		newer=calc(PP[p-1].x,PP[p-1].y,x,y);
		_add(p,newer-older);
	}
	if(p!=PP.size()-1){
		//不是右顶点
		older=sum(p,p+1);
		newer=calc(PP[p+1].x,PP[p+1].y,x,y);
		_add(p+1,newer-older);
	}
	PP[p].x=x;
	PP[p].y=y;
}
////////////////////////////////////线段树
void update(int it,int p,int n){
	if(TT[it].l==TT[it].r){
		TT[it].di=n;
		return;
	}
	int mid=(TT[it].l+TT[it].r)/2;
	if(p<=mid){
		update(2*it,p,n);
	}else{ 
		update(2*it+1,p,n);
	}
	TT[it].di=min(TT[it*2].di,TT[it*2+1].di);
}
void rewrite_tree(int p){
	if(p==0||p==PP.size()-1){
		update(1,p,0);
		return;
	}
	int r,u;
	r=sum(p-1,p+1);//原始数值
	u=calc(PP[p-1].x,PP[p-1].y,PP[p+1].x,PP[p+1].y);//直接连接值
	update(1,p,u-r);
}
///////////////////////////////////////生成
void write_tree(int p,int a,int b){
	TT[p].l=a;
	TT[p].r=b;
	if(a==b){
		return;
	}
	int mid=(a+b)/2;
	write_tree(2*p,a,mid);
	write_tree(2*p+1,mid+1,b);
}
void build(int n){//根据PP生成树状数组和线段树
	for(int i=1;i!=PP.size();++i){
		_add(i,calc(PP[i].x,PP[i].y,PP[i-1].x,PP[i-1].y));
	}
	write_tree(1,0,n-1);
	for(int i=0;i!=PP.size();++i){
		rewrite_tree(i);
	}
}
///////////////////////////////////////维护
int find_tree(int p,int a,int b){
	if(a>b){
		return 0;
	}
	if(TT[p].l==a&&TT[p].r==b){
		return TT[p].di;
	}
	int mid=(TT[p].l+TT[p].r)/2;
	if(b<=mid){
		return find_tree(2*p,a,b);
	}else if(a>mid){
		return find_tree(2*p+1,a,b);
	}else{
		return min(find_tree(2*p,a,mid),find_tree(2*p+1,mid+1,b));
	}
}
void rebuild(int p,int x,int y){
	rewrite_len(p,x,y);
	rewrite_tree(p-1);
	rewrite_tree(p);
	rewrite_tree(p+1);
	#if defined wolf
	for(int i=1;i!=PP.size();++i){
		cout<<sum(i-1,i)<<"  ";
	}cout<<endl;
	for(int i=0;i!=PP.size();++i){
		cout<<find_tree(1,i,i)<<"  ";
	}cout<<endl;
	#endif
}
int core(int a,int b){
	int ans=sum(a,b);
	//cout<<"sum"<<ans<<endl;
	ans+=find_tree(1,a+1,b-1);
	return ans;
}
///////////////////////////////////////
int main(){
	double n,q;
	fin>>n>>q;
	for(int i=0;i!=n;++i){
		int a,b;
		fin>>a>>b;
		PP.push_back(node(a,b));
	}
	//读入完成
	TT.resize((int)(n*(log(n)/log(2.0)))+5);
	num.resize((int)n+5,0);
	build((int)n);
	#if defined wolf 
	for(int i=1;i!=PP.size();++i){
		cout<<sum(i-1,i)<<"  ";
	}cout<<endl;
	for(int i=0;i!=TT.size();++i){
		if(TT[i].di==999999999){
			continue;
		}
		cout<<TT[i].l<<kk<<TT[i].r<<kk<<TT[i].di<<endl;
		//cout<<find_tree(1,i-1,i)<<"  ";
	}cout<<endl;
	#endif
	for(int i=0;i!=q;++i){
		char t;
		fin>>t;
		if(t=='U'){
			int a,b,c;
			fin>>a>>b>>c;
			rebuild(a-1,b,c);
		}else{
			int a,b;
			fin>>a>>b;
			fout<<core(a-1,b-1)<<endl;
		}
	}
	//-------------------------*/
	#if defined wolf
	cout<<endl<<(double)clock()/CLOCKS_PER_SEC<<'s'<<endl;
	#endif
	return 0;
}
//Designed by wolf
//Wed Apr 22 2015