树状数组维护前驱后继+简易倍增，不知道哪里挂了

#include<iostream>
#include<algorithm>
#include<cmath>
#define N 100005
#define int long long
using namespace std;
long long xa[N][20],xb[N][20];
double minn=1e9+5;
int a1,b1,ans=N,fa[N][20],a[N],id[N],n,h[N],m,c[140000],ls[N],x,up[N],dn[N],fst[N],scd[N];
void lsh()//离散化 
{
	sort(ls+1,ls+1+n);
	for(int i=1;i<=n;i++)
	{
		h[i]=lower_bound(ls+1,ls+1+n,h[i])-ls;//无误 
		id[h[i]]=i;
	}
	a[n+1]=ls[n+1]=5e9+5;
	a[n+2]=ls[n+2]=a[N]=-5e9-5;
}
int dis(int posa,int posb)
{
	return abs(a[posa]-a[posb]);
}
//tree 
int lowbit(int x)
{
	return x&-x;
}
void upd(int x,int k)
{
	while(x<=n)
	{
		c[x]+=k;
		x+=lowbit(x);
	}
}
int getsum(int x)
{
	int sum=0;
	while(x)
	{
		sum+=c[x];
		x-=lowbit(x);
	}
	return sum;
}
int kth(int x)
{
	int now=0,sum=0;
	for(int i=17;i>=0;i--)
	{
		if(now+(1<<i)<=n&&sum+c[now+(1<<i)]<x)
		{
			sum+=c[1<<i];
			now+=(1<<i);
		}
	}
	return now+1;
}
//
void mem()//求出第一第二近 
{
	for(int i=n;i>=1;i--)
	{
		upd(h[i],1);
		int res=getsum(h[i]);
		if(res<n-i+1)
		{
			up[i]=id[kth(res+1)];
		}
		if(res>1)dn[i]=id[kth(res-1)];
		if(up[i]==0)up[i]=n+1;
		if(dn[i]==0)dn[i]=n+2; 
	}
	for(int i=n;i>=1;i--)
	{
		if(a[i]-a[dn[i]]<=a[up[i]]-a[i])
		{
			fst[i]=dn[i];
			if(a[i]-a[dn[dn[i]]]<=a[up[i]]-a[i])
			{
				scd[i]=dn[dn[i]];
			}
			else scd[i]=up[i];
		}
		else
		{
			fst[i]=up[i];
			if(a[i]-a[dn[i]]<=a[up[up[i]]]-a[i])
			{
				scd[i]=dn[i];
			}
			else scd[i]=up[up[i]];
		}
	}
	for(int i=1;i<=n;i++)
	{
		fa[i][0]=fst[scd[i]];
		xa[i][0]=dis(i,scd[i]);
		xb[i][0]=dis(scd[i],fst[scd[i]]);
	}
	for(int i=1;i<=17;i++)
	{
		for(int j=1;j<=n;j++)
		{
			fa[j][i]=fa[fa[j][i-1]][i-1];
			xa[j][i]=xa[j][i-1]+xa[fa[j][i-1]][i-1];
			xb[j][i]=xb[j][i-1]+xb[fa[j][i-1]][i-1];
		}
	}
}
int binary(int pos,int x)
{
	a1=b1=0;
	for(int i=17;i>=0;i--)
	{
		if(fa[pos][i]<=n&&fa[pos][i]>0&&xa[pos][i]+xb[pos][i]<x)
		{
			a1+=xa[pos][i];
			b1+=xb[pos][i];
			x-=xa[pos][i]+xb[pos][i];
			pos=fa[pos][i];
		}
	}
	if(x>=xa[pos][0])a1+=xa[pos][0];
}
signed main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>h[i];
		a[i]=ls[i]=h[i];
	}
	lsh();
	mem();
	cin>>x>>m;
	for(int i=1;i<=n;i++)
	{
		binary(i,x);
		if(b1==0)
		{
			if(a[ans]<a[i]&&minn==1e9+5)ans=i;
		}
		else
		{
			if(a1*1.0/b1<minn||(a1*1.0/b1==minn&&a[ans]<a[i]))minn=a1*1.0/b1,ans=i;
		}
	}
	cout<<ans<<"\n";
	while(m--)
	{
		int s,x;
		cin>>s>>x;
		binary(s,x);
		cout<<a1<<" "<<b1<<"\n";
	}
}