自动搬运

查看原文

来自洛谷，原作者为

	firefly13163 我梦见一片焦土，一株破土而生的新蕊

搬运于2025-08-24 22:57:57，当前版本为作者最后更新于2025-07-31 17:27:54，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题意

给定顺序排列的 $N$ 个城市，每天 $0\sim T-1$ 共 $T$ 个时间点，该天的时间点 $T-1$ 后是下一天的时间点 $0$。 对于 $1\sim N-1$ 中的编号为 $i$ 的城市，从该城市移动至下一个城市的航班有 $M_i$ 种，第 $j$ 种覆盖的时间段是当天的时间点 $A_{i,j}$ 至 $B_{i,j}$ 。 多次询问从 $L$ 出发（任选出发时间）至 $R$ 所需最短时间。

题解

首先考虑以下情形，我们在某个时间点到达了一个城市，现在需要移动到下一个城市，那么我们如果选择在某一个时间点移动到下一个城市，到达的时间点一定要尽可能的早。显然，更早到达意味着更多的选择，方案必然更优。

那么推广该情形，当到达时间点一定，移动时间也就确定了。据此，回到问题，当我们确定了从 $L$ 出发的时间点，就可以确定到达 $R$ 所需的最短时间。

这种确定性的移动方式，以及多次询问，让我们自然地想到倍增优化，每种航班分别编号，将每种航班进行 $2^k$ 次移动的信息存入表内，可以较为方便地查询。

但我们发现这样做的时间复杂度是错误的，若某个城市的 $M$ 很大，我们在查表的时候就需要查询大量的航班信息，无法通过。

此时注意到 $\sum M \le 10^5$，考虑根号分治。

$M> \sqrt{N}$ 的点不会超出 $\sqrt{N}$ 个（默认 $M$ 和 $N$ 同阶），我们考虑如何处理这些点的答案。

为了减少空间开支，我们将询问离线后对每个上述点单独处理。

对于点 $x$，设 $dp_i$ 为从 $x$ 出发，到达编号为 $i$ 的航班的最短时间（这里我们将航班提前标号了）。转移是简单的，借用之前预处理出的每种航班进行一次移动的信息，我们可以得到下一次航班的编号，进行由已知推未知的 $dp$。

然后对于每个城市的答案计算，也是简单的，对于城市 $y$ ，设 $DP_y$ 为从 $x$ 移动到 $y$ 的最短时间，有 $DP_y=\min{dp_j+len_j}$，其中，航班 $j$ 属于城市 $y-1$，$len_j$ 是航班 $j$ 覆盖的时间段长度。

这样，对于 $M\le \sqrt{N}$ 的点，我们可以查表倍增，在 $O(\sqrt{N}\log{N})$ 的时间内完成单次询问。对于 $M> \sqrt{N}$ 的点，我们可以用总时间复杂度为 $O(N \sqrt{N})$ 的 $dp$ 离线处理。

然后就是一些细节的处理：

1. 若某航班完全包含另一种航班，则该航班可以直接舍弃。显然，我们会选择被它完全包含的航班，该航班出发时间更晚，到达时间更早，显然更优。

2. 注意两趟航班之间等待时间的处理，代码里选择的是记录从航班 $i$ 已经移动了 $2^k$ 次，到达某个城市，即将选择移动到下一个城市的航班时，此时的时间点是该航班的出发时间，这整个过程花费的时间，因此可以看到，代码在处理答案的时候，是先从 $L$ 移动到 $R-1$，也就是移动 $R-L$ 次，然后再加上下一次航班的时间。

3. 我们发现这两类航班数量的城市的询问，其涉及的时间复杂度是不同的，所以为了平衡时间复杂度，可能需要稍微调整一下处理标准，如果被卡了可以尝试手动设置标准。

代码写的比较丑，但还是放一下。

/*

01010101  01010  10101	 010101  01010101  0      1	    1
1           1	 0    0  1		 1		   1       0   0
01010101	0	 10101	 010101  01010101  0	    1 1
1			1	 01		 1		 1         1 	     0	
0		  	0	 1 01	 0		 0         0	     1
1		  10101  0  0101 101010  1         1010101   0

*/

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
#define ll long long

using namespace std;

const int N=5e5+10,lim=1e2;
//手动设置标准，平衡时间
const ll inf=1e18;

int n,m;
ll t;
int sz[N],belong[N];
bool flag[N];
int nxt[N][21];
ll d[N][21];
int tot;
ll dp[N],DP[N],ans[N];

struct flight{
    int st,ed;
    //航班出发时间和到达时间
    ll len;
    //航班覆盖时间段长度
};

struct que{
    int r;
    //对于M较大的点，我们离线询问右端点
    int id;
};

vector<flight> f[N];
vector<int> id[N];
//航班编号
vector<que> q[N];

inline bool flight_cmp(flight a,flight b){
    if(a.ed!=b.ed){
        return a.ed<b.ed;
    }
    return a.st>b.st;
}
//先按到达时间排，先到的优先，相同的将出发时间晚的排在前面

inline void init1(){
    for(int i(1);i+1<n;++i){
        int j=i+1;
        int y=1;
        for(int x(1);x<=sz[i];++x){
            while(y<sz[j]&&f[j][y].st<f[i][x].ed){
                y++;
            }
            //找到下一个城市第一个出发时间晚于当前到达时间的航班
            if(f[j][y].st<f[i][x].ed){
                nxt[id[i][x]][0]=id[j][1];
                d[id[i][x]][0]=t-f[i][x].ed+f[j][1].st+f[i][x].len;
            }
            //找到了
            else{
                nxt[id[i][x]][0]=id[j][y];
                d[id[i][x]][0]=f[j][y].st-f[i][x].st;
            }
            //没找到，换成第二天第一趟
        }
    }
    for(int k(1);k<=20;++k){
        for(int i(1);i<=tot;++i){
            nxt[i][k]=nxt[nxt[i][k-1]][k-1];
            d[i][k]=d[i][k-1]+d[nxt[i][k-1]][k-1];
            //倍增预处理
        }
    }
}

inline ll query(int i,int j,int len){
    ll res=0;
    len--;
    //先查到前一个城市
    for(int k(20);k>=0;--k){
        if(len>=(1<<k)){
            len-=(1<<k);
            res+=d[i][k];
            i=nxt[i][k];
        }
    }
    return res+f[j-1][i-id[j-1][1]+1].len;
    //再加上当前航班覆盖时间长度
}

inline void init2(){
    for(int i(1);i<n;++i){
        if(sz[i]>lim&&flag[i]){
            for(int j(id[i][1]);j<=tot;++j){
                dp[j]=inf;
            }
            for(int j(id[i][1]);j<=id[i][sz[i]];++j){
                dp[j]=0;
            }
            for(int j(i+1);j<=n;++j){
                DP[j]=inf;
            }
            DP[i]=0;
            //预处理两种dp数组
            for(int j(i);j<n;++j){
                for(int k(1);k<=sz[j];++k){
                    dp[nxt[id[j][k]][0]]=min(dp[nxt[id[j][k]][0]],dp[id[j][k]]+d[id[j][k]][0]);
                    DP[j+1]=min(DP[j+1],dp[id[j][k]]+f[j][k].len);
                }
            }
            for(auto x:q[i]){
                ans[x.id]=DP[x.r];
                //计算答案
            }
        }
    }
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>t;
    for(int i(1);i<n;++i){
        cin>>sz[i];
        f[i].push_back((flight){-1,-1});
        id[i].push_back(0);
        //个人习惯，不喜欢下标从0开始
        vector<flight> temp;
        for(int j(1),a,b;j<=sz[i];++j){
            cin>>a>>b;
            temp.push_back((flight){a,b,b-a});
        }
        sort(temp.begin(),temp.end(),flight_cmp);
        int now=-1;
        for(auto x:temp){
            if(x.st<=now){
                continue;
            }
            //出发时间比之前的更早，到达时间比之前的更晚，不优
            //筛掉完全包含其他航班的航班
            f[i].push_back(x);
            id[i].push_back(++tot);
            //分配编号
            belong[tot]=i;
            //标记所属城市
            now=x.st;
            //更新出发时间最晚值
        }
        sz[i]=f[i].size()-1;
    }
    init1();
    cin>>m;
    for(int i(1),l,r;i<=m;++i){
        ans[i]=inf;
        cin>>l>>r;
        if(l==r){
            ans[i]=0;
            continue;
        }
        if(sz[l]<=lim){
            int len=r-l;
            for(int j(1);j<=sz[l];++j){
                ans[i]=min(ans[i],query(id[l][j],r,len));
                //直接查
            }
        }
        else{
            flag[l]=true;
            q[l].push_back((que){r,i});
            //离线处理
        }
    }
    init2();
    for(int i(1);i<=m;++i){
        cout<<ans[i]<<'\n';
    }
    return 0;
}

后记

其实这个航班的顺序是构成了一个树形结构，考虑从哪些航班会转移到该航班，就相当于一个树上的父子关系，然后就被神秘的树剖做法打败了。