来源

http://blog.csdn.net/lych_cys/article/details/78925907

前言

想了一天没想到一道题，于是开始随便翻翻别人的博客
找到了这个题。。感觉还不错，记录一下

题意

给你n个数，每个点向它两边第一个>=它的数连边，m次询问x->y的最短路

做法

考虑倍增f[i][j],g[i][j]表示i走2^j步能到达的最左/最右的点的位置。然后询问先贪心走x，然后贪心走y即可。
正确性显然把。。肯定是走得越远越好啦

CODE:(偷的）

#include<bits/stdc++.h> 
#define N 100009 
using namespace std;  int n,m,a[N],q[N],f[N][17],g[N][17];  
int main(){  scanf("%d%*d%d",&n,&m);  int i,j,l,r,x,y,u,v,ans;  for (i=1; i<=n; i++) scanf("%d",&a[i]);  q[j=1]=1;  for (i=2; i<=n; i++){  for (; j && a[i]>a[q[j]]; j--);  f[i][0]=q[j]; q[++j]=i;  }  q[j=1]=n;  for (i=n-1; i; i--){  for (; j && a[i]>a[q[j]]; j--);  g[i][0]=q[j]; q[++j]=i;  }  f[1][0]=1; g[n][0]=n;  for (j=1; j<=16; j++)  for (i=1; i<=n; i++){  f[i][j]=min(f[f[i][j-1]][j-1],f[g[i][j-1]][j-1]);  g[i][j]=max(g[f[i][j-1]][j-1],g[g[i][j-1]][j-1]);  }  while (m--){  scanf("%d%d",&x,&y); if (x>y) swap(x,y);  l=r=x; ans=0;  for (i=16; i>=0; i--){  u=min(f[l][i],f[r][i]); v=max(g[l][i],g[r][i]);  if (v<y){ l=u; r=v; ans|=1<<i; }  }  x=r; l=r=y;  for (i=16; i>=0; i--){  u=min(f[l][i],f[r][i]); v=max(g[l][i],g[r][i]);  if (u>x){ l=u; r=v; ans+=1<<i; }  }  printf("%d\n",ans);  }  return 0;  
}