专栏文章

题解：P3113 [USACO14DEC] Marathon G

RRed_river
P3113题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mipe1zrx
此快照首次捕获于
2025/12/03 10:29
3 个月前
此快照最后确认于
2025/12/03 10:29
3 个月前
查看原文

题目大意

马拉松路线由 NN 个检查点组成，选手必须按顺序经过每个检查点。有两种操作：
  1. 更新某个检查点的坐标。
  2. 查询从检查点 XX 到 YY 的最短路径长度，允许跳过其中一个中间。
要求高效处理这些操作。

思路分析：

对于每个查询操作，我们需要计算 XX 到 YY 的原路径总长度，并允许跳过一个中间点以减少总长度。最优策略是选择跳过能带来最大节省量的点。具体步骤如下：
原路径总和：计算 XX 到 YY 所有相邻点曼哈顿距离之和。
最大节省量：找到中间点 ii，使得跳过 ii 后的路径减少量最大。减少量为：原 i−1i-1 到 ii 和 ii 到 i+1i+1 的距离之和减去 i−1i-1 到 i+1i+1 的曼哈顿距离。
使用线段树维护两个信息：
  1. 区间相邻点曼哈顿距离总和。
  2. 区间内各中间点的最大节省量（存储为负数的最小值）。

线段树算法实现结构：

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

更新操作：

当更新某个点坐标时，会影响其前后相邻点的距离和节省量。需要更新该点及其相邻点的线段树节点。查询操作就是计算原路径总和加上查询中间点的最大节省量，即线段树中最小值。因为我转换成了负数形式，所以是加法。
代码解析：
CPP
#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);
		}
	}
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...