自动搬运

查看原文

来自洛谷，原作者为

	Qiiiiiii_ 人生如逆旅，我亦是行人。

搬运于2025-08-24 22:31:25，当前版本为作者最后更新于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