Journey among Railway Stations

题目大意

n个点在一条直线上，每个点到下一个点需要$t_i$时间，每个点允许通过的时间段是$[u_i,v_i]$。

接下来有m个操作，分为以下三类：

• 问从x点是否能到达y点。
• 将第i个点到下一个点的时间更改为$t_i`$
• 将第i个点的允许通过时间改为$[u_i,v_i]$​

题目链接

思路

事实上，我们可以把两个点合并为一个点（注意这是本题非常重要的思想）

对于每个点，我们需要维护这三个值:

• 允许通过的最晚时间lstArtTime

• 这个点最快什么时候（即 时间点）到下一个点nxtArTime

• 这个点到下一个点所需的时间 （注意与上一个做区分）dis

对于$l, r$两个点，假如从$l$点的最早允许通过的点出发，都无法在$r$点最迟允许通过的时间点前到达，那么就无法从$l$走到$r$​。（即 l.nxtArTime > r.lstArTime）

如果能到达，我们可以把他们合并为1个点，设它为N。那么我们的任务就是求出N点的数值。

• N点的最迟到达时间：首先是不能晚于$l$点的最迟到达时间，其次，还要有足够的时间从$l$走到$r$点，即$r$点的最迟通过时间减去从$l$到$r$​点所需的时间。N.lstArTime = max(l.lstArTime, r.lstArTime - l.dis)

• N点最快到达下一个点的时间: 即$l$最快到$r$的时间点再加上$r$​到下一个点所需的时间，与从$r$最快到下一个点的时间点取一个最大值。

  （之所以要比较，是因为从$l$走到$r$，再走到下一个点时，不一定满足 r能够最快到达下一个点时，所需要的条件）。

  N.nxtArTime = max(l.nxtArTime + r.dis, r.nxtArTime)

• N点到下一个点所需时间，那么就简单了，把$l$到$r$的距离，加上$r$​到下一个点的距离。N.dis = l.dis + r.dis。

所以题目就变成如何动态的维护这些点，并且我们已经知道了怎么合并这些点，那么我们就很容易想到利用线段树来维护：

• 每次查询其实就是查询[l,r]之间的点是否合法，因为其中有一个地方无法通过，那么整个区间就会不合法
• 对于修改操作，对于线段树来说就是单点修改。

代码

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

const int maxN = 2e6 + 5;
long long INF = 0x3f3f3f3f;


int n, q, T;
long long u[maxN], v[maxN], d[maxN];

struct SegmentTree {
    long long lstArTime, nxtArTime, dis;
}t[maxN << 2];

SegmentTree operator +(SegmentTree l, SegmentTree r) { //把合并操作转变为+，十分方便(确信)
    if (l.nxtArTime > r.lstArTime) {
        return { -1, INF, INF}; //不合法就是-1
    }
    return {
        max(min(l.lstArTime, r.lstArTime - l.dis), -1LL), 
        min(max(l.nxtArTime + r.dis, r.nxtArTime), INF), //需要和最大值作比较，方便不合法情况的合并
        min(l.dis + r.dis, INF)
    };
}

void init(int x) //据说这叫ZKW线段树(%ZKW)，就是建树和单点修改都可以使用这个函数。
{
    int l = 1, r = n,k = 1;
    while(l != r) {
        int mid = (l + r) >> 1;
        if(x <= mid) {
            k <<= 1;
            r = mid;
        }
        else {
            l = mid + 1;
            k  = k << 1 | 1;
        }
        t[k] = {v[x], min(u[x] + d[x], INF), d[x]};
    }
    while(k >>= 1)
        t[k] = t[k << 1] + t[k << 1 | 1];
}
//接下来是查询操作，把要查询的点[l, r - 1]合并为一个点，来看这个点是否合法，以及是否可以到达下一个点。
//之所以这么做，是因为我们不需要知道r点到达下一个点的时间，只需知道是否可以到达r点
SegmentTree now; //把所有点合并到now

int ql, qr; //题目要求查询的区间。

void dfs(int k, int l, int r)
{
    if(ql <= l && qr >= r) {
        now = now + t[k];
        return ;
    }
    int mid = (l + r) >> 1;
    if(ql <= mid)
        dfs(k << 1, l, mid);
    if(qr > mid)
        dfs(k << 1 | 1, mid + 1, r);
}

bool query(int l, int r)
{
    if(l == r)
        return true;
    ql = l;
    qr = r - 1;
    now = {INF, 0, 0};
    dfs(1, 1, n);
    return now.nxtArTime <= v[r];
}

int main()
{
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        for(int i = 1; i <= n; ++i)
            scanf("%d", &u[i]);
        for(int i = 1; i <= n; ++i)
            scanf("%d", &v[i]);
        for(int i = 1; i < n; ++i)
            scanf("%d", &d[i]);
        for(int i = 1; i <= n; ++i)
            init(i);//建树
        scanf("%d", &q);
        for(int i = 1; i <= q; ++i) {
            int typ, l, r, pos, c;
            scanf("%d", &typ);
            if(typ == 0) {
                scanf("%d%d", &l, &r);
                if(query(l, r))
                    printf("Yes\n");
                else
                    printf("No\n");
            }
            else if(typ == 1) {
                scanf("%d%d", &pos, &c);
                d[pos] = c;
                init(pos); //修改点
            }
            else if(typ == 2) {
                scanf("%d%d%d", &pos, &l, &r);
                u[pos] = l; v[pos] = r;
                init(pos);
            }
        }
    }
    return 0;
}

• 本文作者： 水蓝络合物
• 本文链接： https://miku39393939.github.io/2021/08/03/Journey-among-Railway-Stations/
• 版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！