题目：https://www.luogu.org/problemnew/show/P1081
真是倍增好题！
预处理：f[i][j] 表示从 i 点开始走 2^j 次 AB (A,B各走一次)到达的点；
sta[i][j] 表示从 i 点开始走 2^j 次 AB 后 A 走过的总路程；stb 为 B 的；
首先要找到 2^0 位置上的，也就是右边最近的和次近的点；
先把点按海拔排序，那么最近点和次近点一定在 i-2 , i-1 , i+1 , i+2 这四个位置；
又不能找到 i 之前的点，所以需要支持查询周边四个值并且可以删除的数据结构，可以用双向链表(用结构体存一个 l 和 r 即可)；
然后倍增预处理出 f , sta , stb 数组，倍增查询即可；
倍增预处理时把 f 写成 sta,stb 改了好久囧...还是不能对应照抄上面一行啊...
还有一定注意预处理的倍增要外层 j 内层 i ！
代码如下：
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; typedef long long ll; int const maxn=1e5+5,inf=1e9; int n,m,f[maxn][20],h[maxn],p[maxn],na[maxn],nb[maxn]; ll sta[maxn][20],stb[maxn][20]; struct N{int id,h,l,r;}d[maxn]; bool cmp(N x,N y){return (x.h==y.h)?x.id<y.id:x.h<y.h;} bool lf(int x,int l,int r)//是否选 l { if(!l)return 0; if(!r)return 1; return d[x].h-d[l].h<=d[r].h-d[x].h;//= } void init() { for(int i=1;i<=n;i++) { f[i][0]=nb[na[i]]; sta[i][0]=abs(h[i]-h[na[i]]); stb[i][0]=abs(h[f[i][0]]-h[na[i]]); } for(int j=1;j<20;j++)//外j内i for(int i=1;i<=n;i++) { f[i][j]=f[f[i][j-1]][j-1]; // sta[i][j]=sta[i][j-1]+sta[sta[i][j-1]][j-1]; // stb[i][j]=stb[i][j-1]+stb[stb[i][j-1]][j-1]; sta[i][j]=sta[i][j-1]+sta[f[i][j-1]][j-1];//f!囧 stb[i][j]=stb[i][j-1]+stb[f[i][j-1]][j-1]; } } void get(int p,ll x,ll &a,ll &b)//ll { a=0; b=0; ll d=0; for(int i=19;i>=0;i--) if(f[p][i]&&d+sta[p][i]+stb[p][i]<=x) { a+=sta[p][i]; b+=stb[p][i]; d+=sta[p][i]+stb[p][i]; p=f[p][i]; } if(na[p]&&d+sta[p][0]<=x)a+=sta[p][0];//A再走一步 } int main() { scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",&h[i]),d[i].h=h[i],d[i].id=i; sort(d+1,d+n+1,cmp); for(int i=1;i<=n;i++)p[d[i].id]=i,d[i].l=i-1,d[i].r=i+1; d[1].l=d[n].r=0; for(int i=1;i<=n;i++) { int j=p[i],l=d[j].l,r=d[j].r; if(lf(j,l,r))nb[i]=d[l].id,na[i]=(lf(j,d[l].l,r)?d[d[l].l].id:d[r].id);//id else nb[i]=d[r].id,na[i]=(lf(j,l,d[r].r)?d[l].id:d[d[r].r].id); if(l)d[l].r=r; if(r)d[r].l=l;//删除j } init(); int ans; ll x; double mn=inf; scanf("%lld%d",&x,&m); ll a,b; for(int i=1;i<=n;i++) { get(i,x,a,b); if(!b)continue; double k=1.0*a/b; if(mn>k)mn=k,ans=i; else if(mn==k&&h[ans]<h[i])ans=i; } printf("%d\n",ans); for(int i=1,x,p;i<=m;i++) { scanf("%d%lld",&p,&x); get(p,x,a,b); printf("%lld %lld\n",a,b); } return 0; }
原文：https://www.cnblogs.com/Zinn/p/9381345.html