[USACO14DEC] Marathon G-Toy模板网

这篇具有很好参考价值的文章主要介绍了[USACO14DEC] Marathon G。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

洛谷[USACO14DEC] Marathon G

题目大意

$\text{Bessie}$ 设计了一条马拉松路线，有 $N$ 个点。

$\text{Bessie}$ 有 $q$ 次操作，每次操作是修改或询问。每次修改会修改一个点的坐标，每次询问是选手跑过一条子路径的时间，一条子路线是整条路线中包含若干连续点的一段。一个单位的时间可以跑一个单位的距离，选手可以省略一个点不跑，但这个点不能是这条子路径的起点或终点。

相邻两个点 $x_1,y_1)$ 和 $x_2,y_2)$ 的距离为 $x_1-x_2|+|y_1-y_2|$ 。

$1\leq n\leq 10^5,1\leq q\leq 10^5$

题解

用线段树维护子路径的长度和这条子路径上删除一个点能够减少的最大距离。

那么，修改就修改线段树上对应位置的值，查询就求这一段子路径的距离和子路径上删除一个点能够减少的最大距离，两者相减即可得到答案。

时间复杂度为 $O((n+q)\log n)$ 。文章来源地址https://www.toymoban.com/news/detail-606229.html

code

#include<bits/stdc++.h>
#define lc k<<1
#define rc k<<1|1
using namespace std;
int n,q,ans,mx,a[100005],b[100005],tr[500005],sum[500005];
int dis(int i,int j){
	return abs(a[i]-a[j])+abs(b[i]-b[j]);
}
void build(int k,int l,int r){
	if(l==r){
		if(l==1||l==n) tr[k]=0;
		else tr[k]=dis(l-1,l)+dis(l,l+1)-dis(l-1,l+1);
		sum[k]=dis(l,l+1);
		return;
	}
	int mid=l+r>>1;
	build(lc,l,mid);
	build(rc,mid+1,r);
	tr[k]=max(tr[lc],tr[rc]);
	sum[k]=sum[lc]+sum[rc];
}
void ch(int k,int l,int r,int x){
	if(l==r&&l==x){
		if(l==1||l==n) tr[k]=0;
		else tr[k]=dis(l-1,l)+dis(l,l+1)-dis(l-1,l+1);
		sum[k]=dis(l,l+1);
		return;
	}
	int mid=l+r>>1;
	if(x<=mid) ch(lc,l,mid,x);
	else ch(rc,mid+1,r,x);
	tr[k]=max(tr[lc],tr[rc]);
	sum[k]=sum[lc]+sum[rc];
}
void find(int k,int l,int r,int x,int y){
	if(l>=x&&r<=y){
		ans+=sum[k];
		mx=max(mx,tr[k]);
		return;
	}
	int mid=l+r>>1;
	if(x<=mid) find(lc,l,mid,x,y);
	if(y>mid) find(rc,mid+1,r,x,y);
}
int main()
{
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&a[i],&b[i]);
	}
	build(1,1,n);
	int v,x,y;
	char c;
	while(q--){
		c=getchar();
		while(c!='U'&&c!='Q') c=getchar();
		if(c=='U'){
			scanf("%d%d%d",&v,&x,&y);
			a[v]=x;b[v]=y;
			ch(1,1,n,v);
			if(v-1>=1) ch(1,1,n,v-1);
			if(v+1<=n) ch(1,1,n,v+1);
		}
		else{
			scanf("%d%d",&x,&y);
			ans=0;mx=0;
			find(1,1,n,x+1,y-1);
			ans=ans+dis(x,x+1)-mx;
			printf("%d\n",ans);
		}
	}
	return 0;
}