[luogu7599]雨林跳跃

为了方便，令$a_{0}=a_{n+1}=\infty$，另外$a_{i}$是两两不同的

记$L_{x}$和$R_{x}$分别为$x$左右两侧第一个比$a_{x}$大的元素位置，可以$o(n)$预处理出来

记$d(x,y)$表示从$x$到$y$的最短路（其中$x\le y$），若不存在$x$到$y$的路径则记$d(x,y)=\infty$

性质：

对于$1\le x<y\le n$（其中$a_{x}<a_{y}$）和$\forall a_{x}\le d\le a_{y}$，令$l=\max_{k\le x,a_{k}\ge d}k$和$r=\min_{k\ge x,a_{k}\ge d}k$，则$x$到$y$的路径上必然经过$l$或$r$，也即$d(x,y)=\min(d(x,l)+d(l,y),d(x,r)+d(r,y))$

利用这条性质，我们可以得到以下结论——

结论1：对于$1\le x<y\le n$，若$\exists x\le i<y,a_{y}<a_{i}$，则不存在$x$到$y$的路径

证明：取性质中$(x,y,d)=(x,y,a_{y})$，显然$l,r\ne y$，即$a_{l},a_{r}>a_{y}$，也即$d(l,y)=d(r,y)=\infty$，代入式子中即可得$d(x,y)=\infty$，不存在$x$到$y$的路径

（事实上，这也是充分条件）

结论2：

对于$1\le x<y\le n$，若$\forall x<i\le y,a_{i}<a_{x}$，则$\forall y<z$且$a_{x}<a_{z},d(x,z)\le d(y,z)$

对于$1\le x<y\le n$，若$\forall x\le i<y,a_{i}<a_{y}$，则$\forall y<z$且$a_{y}<a_{z},d(x,z)\ge d(y,z)$

证明：

（两个情况是类似的，以下只证明第一个情况）

取性质中$(x,y,d)=(y,z,a_{x})$，显然$l=x$且$r=R_{x}$（且$y\ne l,r$），因此$y$到$l$和$r$至少要一步，而$x$到$l$和$r$只需要0或1步，即$d(x,l)=0<d(y,l)$且$d(x,r)=1\le d(y,l)$

因此，即有
$$
d(x,z)\le \min(d(x,l)+d(l,z),d(x,r)+d(r,z))\le \min(d(y,l)+d(l,z),d(y,r)+d(r,z))=d(y,z)
$$

下面，考虑如何求$d(x,y)$（其中$x<y$）：

不妨假设$a_{L_{x}}<a_{R_{x}}$，显然$\forall L_{x}\le i<R_{x},a_{i}<a_{R_{x}}$，接下来分类讨论：

1.若$a_{R_{x}}\le a_{y}$，根据结论2即有$d(R_{x},y)\le d(L_{x},y)$，贪心移动到$R_{x}$

2.若$a_{L_{x}}\le a_{y}<a_{R_{x}}$，显然不能移动到$R_{x}$，只能移动到$L_{x}$

3.若$a_{y}<a_{L_{x}}$，显然$x$不能再移动

重复上述过程，最后第3种情况时若$x=y$即得到最短路，否则无解

再用倍增来优化这个贪心，即可$o(\log n)$求出$x$到$y$的最短路

下面，考虑如何求$\min_{x_{1}\le x\le x_{2}}d(x,y)$（其中$x_{1}\le x_{2}<y$）：

令$p=L_{y}$，根据结论1显然起点$x>p$（否则即存在$a_{y}<a_{p}$），那么若$x_{2}\le p$即无解

令$a_{q}$为区间$[\max(p+1,x_{1}),x_{2}]$的最大值，那么$\forall x\in [\max(p+1,x_{1}),q)$，显然$\forall x\le i<q,a_{i}<a_{q}$且$a_{q}<a_{y}$（$x\in (q,x_{2}]$同理），根据结论2即可得$d(q,y)$即为答案

关于如何求$d(q,y)$前面已经叙述，复杂度为$o(\log n)$

下面，考虑如何求$\min_{x_{1}\le x\le x_{2},y_{1}\le y\le y_{2}}d(x,y)$（其中$x_{1}\le x_{2}<y_{1}\le y_{2}$）：

令$a_{p_{1}}$为区间$[x_{2},y_{1})$的最大值和$q_{1}=R_{p_{1}}$，根据结论1显然终点$y>q_{1}$（否则即存在$a_{y}<a_{p_{1}}$），那么若$q_{1}>y_{2}$即无解，因此不妨设$y_{1}\le q_{1}\le y_{2}$

再令$p_{2}=L_{q_{1}}$和$q_{2}=R_{p_{2}}$，则答案为$\min(\min_{x_{1}\le x\le x_{2}}d(x,q_{1}),\min_{x_{1}\le x\le x_{2}}d(x,q_{2}))$（特别的，若$q_{2}>y_{2}$则后项定义为$\infty$）

关于这个结论，对$p_{2}$分类讨论：

1.若$p_{2}<x_{1}$，取性质中$(x,y,d)=(x,y,a_{q_{1}})$，显然$l=p_{2}$且$r=q_{1}$

当我们到达$l$后，若$q_{2}=R_{l}$不在$[y_{1},y_{2}]$中即无解，否则只需要1步即可到达$q_{2}$

当我们到达$r$后，即已经在$q_{1}=r$

2.若$p_{2}\ge x_{1}$（显然$p_{2}\le x_{2}$），若$q_{2}$在$[y_{1},y_{2}]$中则取$x=p_{2}$和$y=q_{2}$即可（仍以$y_{2}$为终点），否则必然有起点$x>p_{2}$（否则存在$a_{y}<a_{p_{2}}$），之后与第1种情况相同

关于如何求$\min_{x_{1}\le x\le x_{2}}d(x,q)$前面已经叙述，复杂度为$o(\log n)$

最终，总复杂度为$o(n\log n)$，可以通过

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 #define N 200005

 4 #define oo 0x3f3f3f3f

 5 #define L (k<<1)

 6 #define R (L+1)

 7 #define mid (l+r>>1)

 8 int n,a[N],st[N],l[N],r[N],id[N],mn[N][21],mx[N][21],f[N<<2];

 9 bool cmp(int x,int y){

10     return a[x]>a[y];

11 }

12 int get_max(int x,int y){

13     if (a[x]>a[y])return x;

14     return y;

15 }

16 void build(int k,int l,int r){

17     if (l==r){

18         f[k]=l;

19         return;

20     }

21     build(L,l,mid);

22     build(R,mid+1,r);

23     f[k]=get_max(f[L],f[R]);

24 }

25 int query(int k,int l,int r,int x,int y){

26     if ((l>y)||(x>r))return n+1;

27     if ((x<=l)&&(r<=y))return f[k];

28     return get_max(query(L,l,mid,x,y),query(R,mid+1,r,x,y));

29 }

30 void init(int nn,vector<int>v){

31     n=nn;

32     a[0]=oo;

33     for(int i=1;i<=n;i++)a[i]=v[i-1];

34     for(int i=1;i<=n;i++){

35         while ((st[0])&&(a[st[st[0]]]<a[i]))st[0]--;

36         l[i]=st[st[0]];

37         st[++st[0]]=i;

38     }

39     st[0]=0;

40     for(int i=n;i;i--){

41         while ((st[0])&&(a[st[st[0]]]<a[i]))st[0]--;

42         r[i]=st[st[0]];

43         st[++st[0]]=i;

44     }

45     for(int i=1;i<=n;i++){

46         id[i]=i;

47         mn[i][0]=l[i],mx[i][0]=r[i];

48         if (a[mn[i][0]]>a[mx[i][0]])swap(mn[i][0],mx[i][0]);

49     }

50     sort(id+1,id+n+1,cmp);

51     for(int i=1;i<=n;i++){

52         int x=id[i];

53         for(int j=1;j<=20;j++){

54             mn[x][j]=mn[mn[x][j-1]][j-1];

55             mx[x][j]=mx[mx[x][j-1]][j-1];

56         }

57     }

58     build(1,1,n);

59 }

60 int minimum_jumps(int x,int y){

61     int ans=0;

62     for(int i=20;i>=0;i--)

63         if (a[mx[x][i]]<=a[y]){

64             x=mx[x][i];

65             ans+=(1<<i);

66         }

67     for(int i=20;i>=0;i--)

68         if (a[mn[x][i]]<=a[y]){

69             x=mn[x][i];

70             ans+=(1<<i);

71         }

72     if (x!=y)ans=oo;

73     return ans;

74 }

75 int minimum_jumps(int x1,int x2,int y){

76     int p=l[y];

77     if (x2<=p)return oo;

78     int q=query(1,1,n,max(p+1,x1),x2);

79     return minimum_jumps(q,y);

80 }

81 int minimum_jumps(int x1,int x2,int y1,int y2){

82     x1++,x2++,y1++,y2++;

83     int p1=query(1,1,n,x2,y1-1),q1=r[p1],ans=oo;

84     if ((q1)&&(q1<=y2)){

85         ans=minimum_jumps(x1,x2,q1);

86         int p2=l[q1],q2=r[p2];

87         if ((q2)&&(q2<=y2))ans=min(ans,minimum_jumps(x1,x2,q2));

88     }

89     if (ans==oo)ans=-1;

90     return ans;

91 }

巴特西

[luogu7599]雨林跳跃

最新文章

热门文章