细节巨多。
倍增即可。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<set>
#include<cmath>
#include<cstdlib>
#define maxv 200500
#define maxn 100500
#define eps 1e-7
#define inf 0x7f7f7f7f7f7f7f7fLL
using namespace std;
long long n,m,h[maxn],x,y,aft[maxn][],anc[maxv][],dis1[maxv][],dis2[maxv][],hashed[maxn],pos[maxn];
long long ret1=,ret2=,ans;
struct pnt
{
long long ret,dot,rets;
}p[];
set <long long> s;
set <long long> ::iterator it;
double ans1=inf;
bool cmp(pnt x,pnt y)
{
if (x.ret!=y.ret) return x.ret<y.ret;
return x.rets>y.rets;
}
void divide()
{
for (long long i=;i<=n;i++) hashed[i]=h[i];
sort(hashed+,hashed+n+);
for (long long i=;i<=n;i++)
{
h[i]=lower_bound(hashed+,hashed+n+,h[i])-hashed;
pos[h[i]]=i;
}
}
long long ask(long long x,long long y)
{
ret1=;ret2=;
for (long long e=;e>=;e--)
{
if ((ret1+ret2+dis1[x][e]+dis2[x][e]<=y) && (anc[x][e]))
{
ret1+=dis1[x][e];ret2+=dis2[x][e];
x=anc[x][e];
}
}
}
void update(long long x)
{
if (!ret1) return;
if ((double)ret2/ret1<ans1) {ans1=(double)ret2/ret1;ans=x;}
else if (((double)ret2/ret1-ans1<=eps) && (hashed[h[ans]]<hashed[h[x]])) ans=x;
}
int main()
{
scanf("%lld",&n);
for (long long i=;i<=n;i++) scanf("%lld",&h[i]);
divide();
for (long long i=n;i>=;i--)
{
for (long long j=;j<=;j++) p[j].dot=p[j].ret=inf;
it=s.lower_bound(h[i]);
if (it!=s.end())
{
p[].ret=hashed[h[pos[*it]]];p[].dot=pos[*it];
if (++it!=s.end()) {p[].ret=hashed[h[pos[*it]]];p[].dot=pos[*it];}
it--;
}
if (it!=s.begin())
{
it--;
p[].ret=hashed[h[pos[*it]]];p[].dot=pos[*it];
if (it!=s.begin()) {it--;p[].ret=hashed[h[pos[*it]]];p[].dot=pos[*it];it++;}
}
for (int j=;j<=;j++)
{
if (p[j].ret!=inf)
{
p[j].rets=hashed[h[i]]-p[j].ret;
p[j].ret=abs(hashed[h[i]]-p[j].ret);
}
}
sort(p+,p+,cmp);
if (p[].ret!=inf) aft[i][]=p[].dot;
if (p[].ret!=inf) aft[i][]=p[].dot;
s.insert(h[i]);
}
for (long long i=;i<=n;i++)
{
anc[*i-][]=*aft[i][];dis1[*i-][]=abs(hashed[h[aft[i][]]]-hashed[h[i]]);dis2[*i-][]=;
anc[*i][]=max(*aft[i][]-,(long long));dis1[*i][]=;dis2[*i][]=abs(hashed[h[aft[i][]]]-hashed[h[i]]);
}
n*=;
for (long long e=;e<=;e++)
for (long long i=;i<=n;i++)
{
anc[i][e]=anc[anc[i][e-]][e-];
dis1[i][e]=dis1[i][e-]+dis1[anc[i][e-]][e-];
dis2[i][e]=dis2[i][e-]+dis2[anc[i][e-]][e-];
}
scanf("%lld",&x);
for (long long i=;i<=n;i+=)
{ask(i,x);update(i/);}
printf("%d\n",ans);
scanf("%lld",&m);
for (long long i=;i<=m;i++)
{
scanf("%lld%lld",&x,&y);
ask(*x,y);
printf("%lld %lld\n",ret2,ret1);
}
return ;
}