#include <bits/stdc++.h>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=1e5+5;
const int maxm=1e4+5;
const int INF=0x3f3f3f3f;
int n,h[maxn],X0,m,s,x,ga[maxn],gb[maxn],tot,tag,f[40][maxn][2],t,da[40][maxn][2],db[40][maxn][2],ans;
ll ansA=1,ansB=0,A,B;
int temp[10];
set<pii>Set;
set<pii>::iterator it,it2;
int dis(int x,int y) {
return abs(h[x]-h[y]);
}
bool cmp(int x,int y) {
return dis(x,tag)<dis(y,tag)||(dis(x,tag)==dis(y,tag)&&h[x]<h[y]);
}
void Insert() {
if(tag==1) int ha=1;
it=Set.lower_bound(make_pair(h[tag],tag));
it2=it,tot=0;
if(it!=Set.begin()) it--,temp[++tot]=it->second;
if(it!=Set.begin()) it--,temp[++tot]=it->second;
it=it2;
if(it!=Set.end()) temp[++tot]=it->second,it++;
if(it!=Set.end()) temp[++tot]=it->second,it++;
sort(temp+1,temp+tot+1,cmp);
if(tot>=1) gb[tag]=temp[1];
if(tot>=2) ga[tag]=temp[2];
Set.insert(make_pair(h[tag],tag));
}
void dp1() {
for(int i=1; i<=n; i++){
if(ga[i])f[0][i][0]=ga[i];
if(gb[i])f[0][i][1]=gb[i];
}
for(int i=1; i<=n; i++) {
for(int j=0; j<=1; j++) {
if(f[0][i][j]) f[1][i][j]=f[0][f[0][i][j]][1-j];
}
}
for(int i=2; i<=t; i++) {
for(int j=1; j<=n; j++) {
for(int k=0; k<=1; k++) {
if(f[i-1][j][k]) f[i][j][k]=f[i-1][f[i-1][j][k]][k];
}
}
}
}
void dp2() {
for(int i=1; i<=n; i++) {
if(ga[i]) {
da[0][i][0]=dis(i,ga[i]),da[0][i][1]=0;
}
if(gb[i]) {
db[0][i][0]=0,db[0][i][1]=dis(i,gb[i]);
}
}
for(int i=1; i<=t; i++) {
for(int j=1; j<=n; j++) {
for(int k=0; k<=1; k++) {
if(i==1) {
if(f[i][j][k]) da[i][j][k]=da[i-1][f[i-1][j][k]][1-k]+da[i-1][j][k];
if(f[i][j][k]) db[i][j][k]=db[i-1][f[i-1][j][k]][1-k]+db[i-1][j][k];
} else {
if(f[i][j][k]) da[i][j][k]=da[i-1][f[i-1][j][k]][k]+da[i-1][j][k];
if(f[i][j][k]) db[i][j][k]=db[i-1][f[i-1][j][k]][k]+db[i-1][j][k];
}
}
}
}
}
void cal(int s,int x) {
A=B=0;
int k=0;
for(int i=t; i>=0; i--) {
if(A+B+da[i][s][k]+db[i][s][k]<=x&&f[i][s][k]) {
A+=da[i][s][k],B+=db[i][s][k];
if(i==0) k=1-k;
s=f[i][s][k];
}
}
}
int main() {
ios::sync_with_stdio(false);
cin>>n;
t=(log(n)/log(2))+1;
for(int i=1; i<=n; i++) cin>>h[i];
for(int i=n; i>=1; i--) tag=i,Insert();
dp1();
dp2();
cin>>X0>>m;
for(int i=1; i<=n; i++) {
cal(i,X0);
if(B==0) A=1;
if(ansA*B>A*ansB||(ansA*B==A*ansB&&h[ans]<h[i])) {
ansA=A,ansB=B,ans=i;
}
}
cout<<ans<<endl;
while(m--) {
cin>>s>>x;
cal(s,x);
cout<<A<<" "<<B<<endl;
}
return 0;
}

本场比赛压轴题，很恶心的倍增优化dp。
题解链接：https://www.jianshu.com/p/fdb41c13d11f