题解：P3113 [USACO14DEC] Marathon G

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

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

代码：

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int maxn=145141;
int n,q;
pii mat[maxn];
int delta[2*maxn];
int dist[2*maxn];
int qa,qb;
int getd(int a,int b){
	return abs(mat[a].first-mat[b].first)+abs(mat[a].second-mat[b].second);
}
void build(int rt,int a,int b){
	if(a>b)return;
	if(a==b){
		if(a<n-1)delta[rt]=getd(a,a+1)+getd(a+1,a+2)-getd(a,a+2);
		else delta[rt]=0;
		if(a<n)dist[rt]=getd(a,a+1);
		else dist[rt]=0;
		return;
	}
	int mid=(a+b)/2;
	build(rt*2,a,mid);
	build(rt*2+1,mid+1,b);
	delta[rt]=max(delta[rt*2],delta[rt*2+1]);
	dist[rt]=dist[rt*2]+dist[rt*2+1];
}
int query_dist(int rt,int a,int b){
	if(a>qb||b<qa)return 0;
	if(qa<=a&&b<=qb)return dist[rt];
	int mid=(a+b)/2;
	return query_dist(rt*2,a,mid)+query_dist(rt*2+1,mid+1,b);
}

int query_delta(int rt,int a,int b){
	if(a>qb||b<qa)return 0;
	if(qa<=a&&b<=qb)return delta[rt];
	int mid=(a+b)/2;
	return max(query_delta(rt*2,a,mid),query_delta(rt*2+1,mid+1,b));
}

void update_dist(int rt,int a,int b){
	if(a>qb||b<qa)return;
	if(qa<=a&&b<=qb){
		if(a>=1&&a<n)dist[rt]=getd(a,a+1);
		else dist[rt]=0;
		return;
	}
	int mid=(a+b)/2;
	update_dist(rt*2,a,mid);
	update_dist(rt*2+1,mid+1,b);
	dist[rt]=dist[rt*2]+dist[rt*2+1];
}
void update_delta(int rt,int a,int b){
	if(a>qb||b<qa)return;
	if(qa<=a&&b<=qb){
		if(a>=1&&a<n-1)delta[rt]=getd(a,a+1)+getd(a+1,a+2)-getd(a,a+2);
		else delta[rt]=0;
		return;
	}
	int mid=(a+b)/2;
	update_delta(rt*2,a,mid);
	update_delta(rt*2+1,mid+1,b);
	delta[rt]=max(delta[rt*2],delta[rt*2+1]);
}

int main(){
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		cin>>mat[i].first>>mat[i].second;
	}
	build(1,1,n);
	for(int i=0;i<q;i++){
		char c;
		cin>>c;
		if(c=='Q'){
			cin>>qa>>qb;
			qb--;
			int tot=query_dist(1,1,n);
			qb--;
			int del=query_delta(1,1,n);
			cout<<tot-del<<'\n'; 
		}else{
			int ix,pa,pb;
			cin>>ix>>pa>>pb; 
			mat[ix].first=pa;
			mat[ix].second=pb;
			for(int j=ix-1;j<=ix;j++){
				qa=j;
				qb=j;
				update_dist(1,1,n);
			}
			for(int j=ix-2;j<=ix;j++){
				qa=j;
				qb=j;
				update_delta(1,1,n);
			}
		}
	}
}