题解 P7599 [APIO2021] 雨林跳跃
Published:
(下文中 $\max[s,t]$ 表示区间 $[s,t]$ 中最大值，出于方便，$A/B/C/D$ 可能表示端点或者点值，请根据语境判断 )
对于每个点左右可跳到的点直接二分+$ST$ 表求区间最值可以做到 $O(n\log n)$ ，当然，你也可以用线段树上二分完成此部分，时间复杂度依旧是 $O(n\log n)$ 。接下来跟着数据思考即可。
先抛开最优解要求，我们思考如何构造一组合法解。取出 $[A,B]$ 的右端点 $B$ ，然后一直往右边跳，如果能到达 $[C,D]$ 即有解。该策略在 $\max [B,C-1] < \max[C,D]$ 时一定可行。反之，在不满足上述条件的情况， $[A,B]$ 之间任意一个值跳的时候都会被 $[B,C-1]$ 中某一个值给挡住，或者直接越过 $[C,D]$ 这个区间。
那么，有解的充要条件就是 $\max[B,C-1]<\max[C,D]$ 。
根据上述策略构造出的解不一定是最优的，我们来思考如何优化我们的策略。我们优先考虑 $A=B,C=D$ 的情况 。我们从 $A$ 起跳的时候，跳到的任何一个柱子都不能高于 $C$ ，否则就会导致无法到达 $C$ 。在保证每次跳的柱子不超过 $C$ 的情况下，我们优先跳更高的那个柱子(由于更高的柱子接下来可以跳跃的位置包含较低的柱子，这显然不会使答案变劣)。当我们无法跳更高的柱子的时候，我们就可以一心一意地往右跳(这个情况的决策已经非常单一了)。
我们将每个点可以跳到的更高的柱子视为其父亲，上述策略第一步就相当于树上倍增。而第二步则是序列上倍增。用两个倍增数组即可实现。这一步的时间复杂度是 $O(q\log n)$ 。
接下来，我们将问题扩展到 $A\neq B$ 的情况。根据贪心思想容易想到，我们只需要 $\max [A,B]$ 。但这个值并不一定对，因为可能 $\max[A,B]>C$ ，这就会导致我们无法达到目标位置。所以，在贪心之前，我们得先保证所选起点合法，其次才是贪心取最大值。由于要往右跳，所以合法区间一定是原区间的一段后缀。对于一段区间 $[X,B]$ ，若 $\max[X,B]<C$ ，那么这段区间一定全部合法。二分找出最长后缀，然后在这个后缀中取最大值即可。这一步是在线段树上二分，所以时间复杂度依旧是 $O(q\log n)$ 。(考场上，在预处理阶段，由于我懒得写 $ST$ 表求区间最值反而用线段树上二分写了这一部分，为了防止我调用混淆，我就没写线段树上二分，直接朴素的二分+线段树，时间复杂度是 $O(q\log^2 n)$ ，本题时限开得很大，所以我就很放心的牺牲了一点时间复杂度 )
最后，我们只需要将问题扩展到 $C\neq D$ 的情况。这个时候，我们发现有效的值似乎也只有 $\max [C,D]$ 。但如果我们拿这个最大值套用上述的策略又会出现一个小问题：可能我已经能跳到了 $[C,D]$ 之间，但我却一直盯着最大值，这样会导致答案变劣。这里就不得不修正决策中第一次在树上倍增中所选定的筏值：这里更准确来说不是 $\max[C,D]$，而是 $\max[B,C-1]$ 。当我们即将越过这个筏值的时候也就表明我们将获得答案(在 $C=D$ 的情况下，这个筏值和 $C$ 几乎等价)。
综合上面所有的写法即可拿到满分，总时间复杂度 $O(p\log n)$，给出的代码的时间复杂度是 $O(p\log^2n)$ (少写了一个线段树上二分)。
(赛时调试了不少时间，代码写得很丑，读起来可能很痛苦，而且该写法时间复杂度不是很优秀，由于评测机的关心，我直到出成绩之前都不知道自己过了 )
#include<bits/stdc++.h>
#define ll long long
#define FOR(i,a,b) for(int i=(a),i##i=(b);i<=i##i;++i)
#define ROF(i,a,b) for(int i=(a),i##i=(b);i>=i##i;--i)
using namespace std;
const int N=2e5+10;
typedef vector<int> VT;
void init(int N, std::vector<int> H);
int minimum_jumps(int A, int B, int C, int D);
int n,tzb[N],mx[N<<2],inf;
VT h;
#define ls (rt<<1)
#define rs (rt<<1|1)
void build(int rt,int l,int r){
if(l==r) return mx[rt]=h[l],void();
int mid=(l+r)>>1;
build(ls,l,mid),build(rs,mid+1,r);
mx[rt]=max(mx[ls],mx[rs]);
}
int ask_max(int rt,int l,int r,int L,int R){
if(L>R) return 0;
if(L<=l&&r<=R) return mx[rt];
int mid=(l+r)>>1,as=0;
if(L<=mid) as=max(as,ask_max(ls,l,mid,L,R));
if(R>mid) as=max(as,ask_max(rs,mid+1,r,L,R));
return as;
}
int res;
void dfs_nxt(int rt,int l,int r,int k){
if(mx[rt]<=k) return ;
if(l==r) return res=l,void();
int mid=(l+r)>>1;
if(mx[ls]>k) dfs_nxt(ls,l,mid,k);
else dfs_nxt(rs,mid+1,r,k);
return ;
}
void ask_nxt(int rt,int l,int r,int L,int R,int k){
if(L>R) return ;
if(L<=l&&r<=R) return dfs_nxt(rt,l,r,k);
int mid=(l+r)>>1;
if(L<=mid) ask_nxt(ls,l,mid,L,R,k);
if(R>mid&&res==inf) ask_nxt(rs,mid+1,r,L,R,k);
return ;
}
void dfs_pre(int rt,int l,int r,int k){
if(mx[rt]<=k) return ;
if(l==r) return res=l,void();
int mid=(l+r)>>1;
if(mx[rs]>k) dfs_pre(rs,mid+1,r,k);
else dfs_pre(ls,l,mid,k);
return ;
}
void ask_pre(int rt,int l,int r,int L,int R,int k){
if(L>R) return ;
if(L<=l&&r<=R) return dfs_pre(rt,l,r,k);
int mid=(l+r)>>1;
if(R>mid) ask_pre(rs,mid+1,r,L,R,k);
if(L<=mid&&res==inf) ask_pre(ls,l,mid,L,R,k);
return ;
}
int fa[21][N],nx[21][N],tp2[N],dep[N],dep2[N],root;
VT tr[N],ed[N];
void dfs(int u){
dep[u]=dep[fa[0][u]]+1;
int z=tr[u].size(),v=0;
FOR(i,0,z-1){
v=tr[u][i];
dfs(v);
}
return ;
}
void dfs2(int u){
dep2[u]=dep2[nx[0][u]]+1;
int z=ed[u].size(),v=0;
FOR(i,0,z-1){
v=ed[u][i];
dfs2(v);
}
return ;
}
void init(int nn,VT hh){
n=nn-1,h=hh,inf=n+2;
h.push_back(0),h.push_back(0),h.push_back(0);
FOR(i,0,n) tzb[h[i]]=i,fa[0][i]=-1,nx[0][i]=i;
build(1,0,n);
FOR(i,0,n){
int f1=0,f2=0;
res=inf,ask_pre(1,0,n,0,i-1,h[i]),f1=res;
res=inf,ask_nxt(1,0,n,i+1,n,h[i]),f2=res;
if(h[f1]>h[f2]) fa[0][i]=f1,tr[f1].push_back(i);
else fa[0][i]=f2,tr[f2].push_back(i);
if(f1==inf&&f2==inf) fa[0][i]=i;
if(f2!=inf) nx[0][i]=f2,ed[f2].push_back(i);
}
FOR(i,0,n) if(fa[0][i]==i) root=i;
FOR(i,0,n) if(nx[0][i]==i) dfs2(i);
dfs(root);
FOR(k,1,18) FOR(i,0,n) fa[k][i]=fa[k-1][fa[k-1][i]],nx[k][i]=nx[k-1][nx[k-1][i]];
return ;
}
int ans;
void cal(int u,int C,int w1,int w2){
int v=u;
ROF(k,18,0) if(h[fa[k][v]]<=w1) v=fa[k][v];
if(nx[0][v]<C&&h[fa[0][v]]<=w2) v=fa[0][v];
ans=dep[u]-dep[v];
if(v>=C) return ;
u=v;
ROF(k,18,0) if(nx[k][v]<C) v=nx[k][v];
v=nx[0][v];
ans+=dep2[u]-dep2[v];
return ;
}
int minimum_jumps(int A, int B, int C, int D) {
int mx1=ask_max(1,0,n,B,C-1),mx2=ask_max(1,0,n,C,D);
if(mx1>mx2) return -1;
int l=A,r=B,mid=0,as=inf;
while(l<=r){
mid=(l+r)>>1;
if(ask_max(1,0,n,mid,B)<mx2) r=mid-1,A=mid;
else l=mid+1;
}
int us=ask_max(1,0,n,A,B),nw=tzb[us];
cal(nw,C,mx1,mx2),as=ans;
return as;
}
//7 3
//1 2 6 3 4 5 7
//3 3 6 6
//1 3 5 6
//0 1 2 2
//7 3
//3 2 1 6 4 5 7
//4 4 6 6
//1 3 5 6
//0 1 2 2