题解 P7599 [APIO2021] 雨林跳跃

Qiiiiiii_ · 2021-06-01 22:01:38 · 题解

​ (下文中 \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