分析

emmmm，先考虑70分做法，先 ${n}^{2}$ 处理每个点的最近和次近，每次询问手动模拟。

代码如下

#include <cstdio>
#include <iostream>
#include <algorithm>
#define N 100005
#define LL long long
#define inf 2147483647
using namespace std;
struct node{
int i, v, l, r;
bool operator < (const node & A) const{
return v < A.v;
}
}d[N];
int stA[N][19], stB[N][19], f[N][19], na[N], nb[N], p[N], l, r, j, a, b;
double ans = inf;
LL z = 1;
int zuo(){
if(!l) return 0;
if(!r) return 1;
return d[j].v - d[l].v <= d[r].v - d[j].v;
}
int pd(int l, int r){
if(!l) return d[r].i;
if(!r) return d[l].i;
if(d[r].v - d[j].v >= d[j].v - d[l].v) return d[l].i;
return d[r].i;
}
void work(int p, LL x){
int i;
for(i = 18; i >= 0; i--){
if(f[p][i] && z * (a + b + stA[p][i] + stB[p][i]) <= x){
a += stA[p][i];
b += stB[p][i];
p = f[p][i];
}
}
if(na[p] && z * (a + b + stA[p][0]) <= x) a += stA[p][0];
}
int main(){
int i, n, m, t;
LL x;
scanf("%d", &n);
for(i = 1; i <= n; i++){
d[i].i = i;
scanf("%d", &d[i].v);
}
sort(d + 1, d + i);
for(i = 1; i <= n; i++) p[d[i].i] = i;
for(i = 1; i <= n; i++) d[i].l = i - 1, d[i].r = i + 1;
d[1].l = d[n].r = 0;
for(i = 1; i <= n; i++){
j = p[i]; l = d[j].l; r = d[j].r;
if(zuo()) nb[i] = d[l].i, na[i] = pd(d[l].l, r);
else nb[i] = d[r].i, na[i] = pd(l, d[r].r);
if(l) d[l].r = r;
if(r) d[r].l = l;
}
for(i = 1; i <= n; i++){
f[i][0] = nb[na[i]];
stA[i][0] = abs(d[p[i]].v - d[p[na[i]]].v);
stB[i][0] = abs(d[p[na[i]]].v - d[p[f[i][0]]].v);
}
for(i = 1; i <= 18; i++)
for(j = 1; j <= n; j++){
f[j][i] = f[f[j][i-1]][i-1];
stA[j][i] = stA[j][i-1] + stA[f[j][i-1]][i-1];
stB[j][i] = stB[j][i-1] + stB[f[j][i-1]][i-1];
}
scanf("%lld%d", &x, &m);
for(i = 1; i <= n; i++){
a = b = 0;
work(i, x);
if(b && 1.0 * a / b < ans){
ans = 1.0 * a / b;
t = i;
}
}
printf("%d\n", t);
for(i = 1; i <= m; i++){
a = b = 0;
scanf("%d%lld", &t, &x);
work(t, x);
printf("%d %d\n", a, b);
}
return 0;
}