题解：P10439 [JOISC 2024] 逃生路线 2 (Day4)
firefly13163
·
·
题解
题意
给定顺序排列的 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，考虑根号分治。
为了减少空间开支，我们将询问离线后对每个上述点单独处理。
对于点 $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. 我们发现这两类航班数量的城市的询问，其涉及的时间复杂度是不同的，所以为了平衡时间复杂度，可能需要稍微调整一下处理标准，如果被卡了可以尝试手动设置标准。
代码写的比较丑，但还是放一下。
```cpp
/*
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;
}
```
### 后记
其实这个航班的顺序是构成了一个树形结构，考虑从哪些航班会转移到该航班，就相当于一个树上的父子关系，然后就被神秘的树剖做法打败了。