| 记录编号 |
229766 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
马拉松 |
最终得分 |
100 |
| 用户昵称 |
 liu_runda |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
3.055 s |
| 提交时间 |
2016-02-20 18:32:04 |
内存使用 |
3.89 MiB |
显示代码纯文本
#include<cstdio>
#define min(a,b) a<b?a:b
#define lch(x) x<<1
#define rch(x) x<<1|1
const int maxn=100005;
struct point{
int x,y;
}lst[maxn];
inline int abs(int x){
if(x>=0)return x;
else return -x;
}
int read(){
char ch;int x;bool minus=false;
while(ch=getchar(),(ch>'9'||ch<'0')&&ch!='-');
if(ch=='-'){
minus=true;
ch=getchar();
}
x=ch-48;
while(ch=getchar(),ch<='9'&&ch>='0')x=x*10+ch-48;
if(minus)x=-x;
return x;
}
int dis[maxn];//dis[i]:i号检查站到i+1号的距离
int _dis[maxn];//_dis[i]:检查站i ->i+2的距离
int st_dis[maxn<<2];
int st_delta[maxn<<2];
//实现求不跳过检查站时距离的线段树
void build_dis(int rt,int l,int r){
if(l==r)st_dis[rt]=dis[l];
else{
int mid=(l+r)>>1;
build_dis(lch(rt),l,mid);
build_dis(rch(rt),mid+1,r);
st_dis[rt]=st_dis[lch(rt)]+st_dis[rch(rt)];
}
}
int query_dis(int rt,int l,int r,const int &a,const int &b){
if(a<=l&&r<=b)return st_dis[rt];
else{
int mid=(l+r)>>1;
if(b<=mid)return query_dis(lch(rt),l,mid,a,b);
if(a>mid) return query_dis(rch(rt),mid+1,r,a,b);
return query_dis(lch(rt),l,mid,a,b)+query_dis(rch(rt),mid+1,r,a,b);
}
}
void update_dis(int rt,int l,int r,const int &pos,const int &newdis){
if(l==pos&&r==pos){
st_dis[rt]=newdis;
}else{
int mid=(l+r)>>1;
if(pos<=mid)update_dis(lch(rt),l,mid,pos,newdis);
else update_dis(rch(rt),mid+1,r,pos,newdis);
st_dis[rt]=st_dis[lch(rt)]+st_dis[rch(rt)];
}
}
//实现求最大缩减距离的线段树
void build_delta(int rt,int l,int r){
if(l==r)st_delta[rt]=_dis[l]-dis[l]-dis[l+1];//跳过第l/r号检查站的下一个检查站,变化量为负：缩短
else {
int mid=(l+r)>>1;
build_delta(lch(rt),l,mid);
build_delta(rch(rt),mid+1,r);
st_delta[rt]=min(st_delta[lch(rt)],st_delta[rch(rt)]);
}
}
int query_delta(int rt,int l,int r,int a,int b){
if(a<=l&&r<=b)return st_delta[rt];
else{
int mid=(l+r)>>1;
if(b<=mid)return query_delta(lch(rt),l,mid,a,b);
if(a>mid)return query_delta(rch(rt),mid+1,r,a,b);
return min(query_delta(lch(rt),l,mid,a,b),query_delta(rch(rt),mid+1,r,a,b));
}
}
void update_delta(int rt,int l,int r,int pos,int newdelta){
if(l==pos&&r==pos){
st_delta[rt]=newdelta;
}else{
int mid=(l+r)>>1;
if(pos<=mid)update_delta(lch(rt),l,mid,pos,newdelta);
else update_delta(rch(rt),mid+1,r,pos,newdelta);
st_delta[rt]=min(st_delta[rch(rt)],st_delta[lch(rt)]);
}
}
int main(){
freopen("marathona.in","r",stdin);
freopen("marathona.out","w",stdout);
//input
int n,q,a,b;char buf[5];
n=read();q=read();
int lim=n-1;
for(int i=1;i<=n;++i){
lst[i].x=read();
lst[i].y=read();
}
if(n==1){
goto lb;
}
//init
for(int i=1;i<n;++i){
// printf("%d %d ",abs(lst[i+1].x-lst[i].x),abs(lst[i+1].y-lst[i].y));
dis[i]= abs(lst[i+1].x-lst[i].x) + abs(lst[i+1].y-lst[i].y);
}//printf("\n");
for(int i=1;i<lim;++i)_dis[i]=abs(lst[i+2].x-lst[i].x)+abs(lst[i+2].y-lst[i].y);
//build st
build_dis(1,1,n-1);//跑n-1段
build_delta(1,1,n-2);//有n-2个检查站可跳过
//deal with queries
lb:
while(q--){
scanf("%s",buf);
if(buf[0]=='Q'){
a=read();b=read();
if(a==b)printf("0\n");
else if(a+1==b)printf("%d\n",query_dis(1,1,n-1,a,b-1));
else printf("%d\n",query_dis(1,1,n-1,a,b-1)+query_delta(1,1,n-2,a,b-2));
}else{
a=read();
lst[a].x=read();
lst[a].y=read();
if(n==1)continue;
if(a!=1){
dis[a-1]=abs(lst[a-1].x-lst[a].x) + abs(lst[a-1].y-lst[a].y);
update_dis(1,1,n-1,a-1,dis[a-1]);
}
if(a!=n){
dis[a]=abs(lst[a+1].x-lst[a].x) + abs(lst[a+1].y-lst[a].y);
update_dis(1,1,n-1,a,dis[a]);
}
int delta;
if(a-2>=1){
_dis[a-2]=abs(lst[a-2].x-lst[a].x)+abs(lst[a-2].y-lst[a].y);
delta=_dis[a-2]-dis[a-2]-dis[a-1];
update_delta(1,1,n-2,a-2,delta);
}
if(a-1>=1&&a<n){
_dis[a-1]=abs(lst[a-1].x-lst[a+1].x)+abs(lst[a-1].y-lst[a+1].y);
delta=_dis[a-1]-dis[a-1]-dis[a];
update_delta(1,1,n-2,a-1,delta);
}
if(a<n-1){
_dis[a]=abs(lst[a+2].x-lst[a].x)+abs(lst[a+2].y-lst[a].y);
delta=_dis[a]-dis[a]-dis[a+1];
update_delta(1,1,n-2,a,delta);
}
}
}
fclose(stdin);fclose(stdout);
return 0;
}