题解
模拟，每次二分找下一个钉子，将绳子整除其间距离即可。
Q：时间复杂度为什么是正确的呢？为什么不会出现每次找下一个钉子都恰好只够一个距离的情况（这样单次查询时间为(O(n))）？
A：因为出题人不够毒瘤。假设已经找到了第(i-1)和第(i)根钉子，要想构造上述情况，第(i+1)根钉子最优位置是(i,i-1)两根钉子的中点（感性理解可知无论是左偏还是右偏都会使剩余绳长减小）。而这时最多只有(log(2 imes 10^9))个钉子，(O(n))查询完全可以通过。
代码
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int x[N],z[N],n;
struct node {int v,id;} y[N];
inline int read()
{
int s=0,w=1; char ch=getchar();
while(ch<'0' || ch>'9') {if(ch=='-') w=-1; ch=getchar();}
while(ch>='0' && ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
bool cmp(node a,node b) {return a.v<b.v;}
int solve(int a,int l,bool op)
{
int r,tmp;//1:->,0:<-
if(op) r=y[upper_bound(z+1,z+n+1,x[a]+l)-z-1].id;
else r=y[lower_bound(z+1,z+n+1,x[a]-l)-z].id;
if(r==a) return a;
bool qwq=(l/abs(x[r]-x[a]))%2;//1:相反,0:相同
l%=abs(x[r]-x[a]);
if(qwq) return solve(r,l,op^1);
else return solve(a,l,op);
}
int main()
{
n=read(); int m=read(),a,l;
for(int i=1;i<=n;i++) x[i]=y[i].v=z[i]=read(),y[i].id=i;
sort(y+1,y+n+1,cmp),sort(z+1,z+n+1);
while(m--)
{
a=read(),l=read();
int r=y[upper_bound(z+1,z+n+1,x[a]+l)-z-1].id;
l-=(x[r]-x[a]);
printf("%d
",solve(r,l,0));
}
return 0;
}