自动搬运

查看原文

来自洛谷，原作者为

	Zory 春物粉

搬运于2025-08-24 21:45:25，当前版本为作者最后更新于2017-11-02 21:34:44，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

那个，推广一下个人网站。。

http://zory.cf/2017-12/马拉松赛跑Marathon.html

来源和评测点

USACO14DEC Gold

Luogu3113

题目

【题目大意】

N个点的路线(1<=N<=100,000)，必须按顺序经过。

询问特定的子路线需要多长时间才能跑完，

其中的子路线是从完整路线的检查点中截取的的连续子序列。

牛可能会选择在任何时候跳过一个检查点，但不允许在子路线中跳过第一个或最后一个点

可能修改点的坐标

由于该课程设置在市中心的街道网络中，

两个点之间的距离(x1,y1)和(x2,y2)是由|x1-x2|+|y1-y2|得出的。 【输入格式】

第一行N和Q (1<=Q<=100,000).

下面N行 每个点的坐标(x,y)，大小范围是-1000..1000

下面Q行 每行一个操作

"U I X Y" 修改 点I (1<=I<=N) 的坐标为(X, Y).

"Q I J" 询问从I到J的最短距离（可以跳过除起点、终点外的其他点）(I <= J)

【输出格式】

每个Q输出距离值

【输入样例】

5 5 -4 4 -5 -3 -1 5 -3 4 0 5 Q 1 5 U 4 0 1

U 4 -1 1

Q 2 4 Q 1 4

【输出样例】

11 8 8

分析

使用线段树维护两个完全不同的信息。

值1是每个节点到上一个节点的距离

值2是每个节点被忽略后的收益（一般是负数）

维护值1的和、值2的最小值

每次修改影响两个值1，三个值2

信息的维护用线段树达到log，树状数组则比较麻烦

玄学AC之

本来线段树不忽略编号1，wa几个点都是个位数级别差异

后来想着顺便加速（因为编号1从来不用），结果AC

如果有人知道，可以在讨论区评论一下

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

typedef long long ll;
ll myabs(ll x) {return x>0?x:-x;}
ll mymin(ll x,ll y) {return x<y?x:y;}

const int MAXN=110000;
int n;

struct nod
{
    int l,r,mid,lc,rc;
    ll s,mi;//分别维护值1的和、值2的最小值
}s[MAXN*2];
int ln=0;
int build(int l,int r)
{
    int t=++ln;
    s[t].l=l;s[t].r=r;s[t].mid=(l+r)>>1;
    if(l<r)
    {
        s[t].lc=build(l,s[t].mid);
        s[t].rc=build(s[t].mid+1,r);
    }
    return t;
}
void change1(int w,int x,ll c)
{
    if(s[w].l==s[w].r)
    {
        s[w].s=c;
        return;
    }
    int lc=s[w].lc,rc=s[w].rc;
    if(x<=s[w].mid) change1(lc,x,c);
    else change1(rc,x,c);
    s[w].s=s[lc].s+s[rc].s;
}
void change2(int w,int x,ll c)
{
    if(s[w].l==s[w].r)
    {
        s[w].mi=c;
        return;
    }
    int lc=s[w].lc,rc=s[w].rc;
    if(x<=s[w].mid) change2(lc,x,c);
    else change2(rc,x,c);
    s[w].mi=mymin(s[lc].mi,s[rc].mi);
}
ll ask1(int w,int l,int r)
{
    if(s[w].l==l and s[w].r==r) return s[w].s;
    int lc=s[w].lc,rc=s[w].rc;
    if(r<=s[w].mid) return ask1(lc,l,r);
    if(l>s[w].mid) return ask1(rc,l,r);
    return ask1(lc,l,s[w].mid)+ask1(rc,s[w].mid+1,r);
}
ll ask2(int w,int l,int r)
{
    if(l>r) return 0;
    if(s[w].l==l and s[w].r==r) return s[w].mi;
    int lc=s[w].lc,rc=s[w].rc;
    if(r<=s[w].mid) return ask2(lc,l,r);
    if(l>s[w].mid) return ask2(rc,l,r);
    return mymin(ask2(lc,l,s[w].mid),ask2(rc,s[w].mid+1,r));
}
//值1是每个节点到上一个节点的距离
//值2是每个节点被忽略后的收益（一般是负数）

int xx[MAXN],yy[MAXN];
ll get(int x,int sf)//与往前sf个节点的距离
{
    return myabs(xx[x]-xx[x-sf])+myabs(yy[x]-yy[x-sf]);
}

ll p[MAXN];//顺便存储值
char ss[10];
int main()
{
    int q;scanf("%d%d",&n,&q);
    build(1,n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&xx[i],&yy[i]);
        if(i==1) continue;
        change1(1,i-1,p[i]=get(i,1));
    }
    for(int i=2;i<=n-1;i++) change2(1,i-1,get(i+1,2)-p[i]-p[i+1]);
    
    while(q--)
    {
        scanf("%s",ss);
        if(ss[0]=='Q')
        {
            int x,y;scanf("%d%d",&x,&y);
            printf("%lld\n",ask1(1,x+1-1,y-1)+ask2(1,x+1-1,y-1-1));
        }
        else
        {
            int a;scanf("%d",&a);
            scanf("%d%d",&xx[a],&yy[a]);
            
            //修改值1两处
            change1(1,a-1,p[a]=get(a,1));
            change1(1,a+1-1,p[a+1]=get(a+1,1));
            
            //对应值2三处
            change2(1,a-1-1,get(a,2)-p[a-1]-p[a]);
            change2(1,a-1,get(a+1,2)-p[a]-p[a+1]);
            change2(1,a+1-1,get(a+2,2)-p[a+1]-p[a+2]);
        }
    }
}