J 题 Journey among Railway Stations

蒟蒻看了看dalao的AC代码，理解了dalao的想法，于是就有了这个题解。

题目大意

n个点在一条直线上，每个点到下一个点需要时间，每个点允许通过的时间段是。

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

  • 问从x点是否能到达y点。
  • 将第i个点到下一个点的时间更改为
  • 将第i个点的允许通过时间改为​

题目链接

思路

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

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

  • 允许通过的最晚时间lstArtTime

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

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

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

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

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

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

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

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

  • N点到下一个点所需时间，那么就简单了，把到的距离，加上​到下一个点的距离。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;
}