P3113 [USACO14DEC] Marathon G

题目大意

马拉松路线由 \(N\) 个检查点组成，选手必须按顺序经过每个检查点。有两种操作：

1. 更新某个检查点的坐标。
2. 查询从检查点 \(X\) 到 \(Y\) 的最短路径长度，允许跳过其中一个中间。

要求高效处理这些操作。

思路分析：

对于每个查询操作，我们需要计算 \(X\) 到 \(Y\) 的原路径总长度，并允许跳过一个中间点以减少总长度。最优策略是选择跳过能带来最大节省量的点。具体步骤如下：

原路径总和：计算 \(X\) 到 \(Y\) 所有相邻点曼哈顿距离之和。

最大节省量：找到中间点 \(i\)，使得跳过 \(i\) 后的路径减少量最大。减少量为：原 \(i-1\) 到 \(i\) 和 \(i\) 到 \(i+1\) 的距离之和减去 \(i-1\) 到 \(i+1\) 的曼哈顿距离。

使用线段树维护两个信息：

1. 区间相邻点曼哈顿距离总和。
2. 区间内各中间点的最大节省量（存储为负数的最小值）。

线段树算法实现结构：

每个节点存储：

1. ans：区间曼哈顿距离总和。
2. min：区间内各点节省量的最小值（节省量为负数形式）。

更新操作：

当更新某个点坐标时，会影响其前后相邻点的距离和节省量。需要更新该点及其相邻点的线段树节点。查询操作就是计算原路径总和加上查询中间点的最大节省量，即线段树中最小值。因为我转换成了负数形式，所以是加法。

代码解析：

#include<bits/stdc++.h>
#define wk(x) write(x),putchar(' ')
#define wh(x) write(x),putchar('\n')
#define L (s<<1)
#define R (L|1)
#define mid ((l+r)>>1)
#define int long long
#define N 200005
#define NO printf("Mark is too tall\n")using namespace std;
int n,m,k,jk,ans,sum,num,cnt,tot;
int dis[N],vis[N];void read(int &x)
{x=0;int ff=1;char ty;ty=getchar();while(!(ty>='0'&&ty<='9')){if(ty=='-') ff=-1;ty=getchar();}while(ty>='0'&&ty<='9')x=(x<<3)+(x<<1)+ty-'0',ty=getchar();x*=ff;return;
}void write(int x)
{if(x==0){putchar('0');return;}if(x<0){x=-x;putchar('-');}char asd[201];int ip=0;while(x) asd[++ip]=x%10+'0',x/=10;for(int i=ip;i>=1;i--) putchar(asd[i]);return;
}struct P{int x,y,z;
}v[N];int DIS(int x,int y){return abs(v[x].x-v[y].x)+abs(v[x].y-v[y].y);
}int change(int x){return abs(v[x-1].x-v[x+1].x)+abs(v[x-1].y-v[x+1].y)-DIS(x-1,x)-DIS(x,x+1);
}struct T{int l,r,min,ans;
}tr[N<<2];void build(int s,int l,int r){tr[s].l=l,tr[s].r=r;if(l==r){if(l==n) return;if(l!=1) tr[s].min=change(l);tr[s].ans=DIS(l,l+1);return;}build(L,l,mid);build(R,mid+1,r);tr[s].min=min(tr[L].min,tr[R].min);tr[s].ans=tr[L].ans+tr[R].ans;
}void CHANGE(int s,int l,int r,int x){if(x==l&&x==r){if(l!=n) tr[s].ans=v[l].z=DIS(l,l+1);if(l!=1&&l!=n) tr[s].min=change(l);return;}if(mid>=x) CHANGE(L,l,mid,x);else CHANGE(R,mid+1,r,x);tr[s].min=min(tr[L].min,tr[R].min);tr[s].ans=tr[L].ans+tr[R].ans;
}int query1(int s,int l,int r,int x,int y){if(x<=l&&r<=y) return tr[s].min;int z=2e17;if(mid>=x) z=query1(L,l,mid,x,y);if(mid<y) z=min(query1(R,mid+1,r,x,y),z);tr[s].min=min(tr[L].min,tr[R].min);tr[s].ans=tr[L].ans+tr[R].ans;return z;
}int query2(int s,int l,int r,int x,int y){if(x<=l&&r<=y) return tr[s].ans;int z=0;if(mid>=x) z+=query2(L,l,mid,x,y);if(mid<y) z+=query2(R,mid+1,r,x,y);tr[s].min=min(tr[L].min,tr[R].min);tr[s].ans=tr[L].ans+tr[R].ans;return z;
}signed main()
{read(n),read(m);char ch;int x,y,z;for(int i=1;i<=n;i++) read(v[i].x),read(v[i].y);for(int i=1;i<=n-1;i++) v[i].z=DIS(i,i+1);build(1,1,n);while(m--){ch=getchar();while(ch!='Q'&&ch!='U') ch=getchar();if(ch=='Q'){read(x),read(y);wh(query2(1,1,n,x,y-1)+query1(1,1,n,x+1,y-1));}else{read(x),read(y),read(z);v[x].x=y;v[x].y=z;CHANGE(1,1,n,x);if(x>1) CHANGE(1,1,n,x-1);if(x<n) CHANGE(1,1,n,x+1);}}
}