题解：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);
        }
    }
}