传送门
思路简单码量超凡？
感觉看完题大家应该都知道是倍增sbsbsb题了吧。
首先预处理出从每个点出发如果是AAA走到哪个点，如果是BBB走到哪个点。
然后利用刚刚预处理出的信息再预处理从每个点出发AAA走2i2^i2i次的距离,BBB走2i2^i2i次的距离，A,BA,BA,B走2i2^i2i轮之后到了哪个点。
剩下的询问就跑倍增就行了。
代码：
#include<bits/stdc++.h>
#include<tr1/unordered_map>
#define fi first
#define se second
using namespace std;
inline int read(){
int ans=0,w=1;
char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans*w;
}
typedef pair<int,int> pii;
const int N=1e5+5;
int Ans=0,ansa=0x3f3f3f3f,ansb=0,x0,n,m,h[N],st[N][21],disa[N][21],disb[N][21],nxta[N],nxtb[N];
struct Node{
int id,val;
friend inline bool operator<(const Node&a,const Node&b){return a.val==b.val?h[a.id]<h[b.id]:a.val<b.val;}
};
inline void init(){
set<pii>S;
int tot=0;
Node tmp[5];
tot=0;
for(int pos=n;pos;--pos){
S.insert(pii(h[pos],pos));
if(pos==n)continue;
tot=0;
set<pii>::iterator it=S.find(pii(h[pos],pos));
if(it!=S.begin()){
--it,tmp[++tot]=(Node){it->se,h[pos]-it->fi};
if(it!=S.begin())--it,tmp[++tot]=(Node){it->se,h[pos]-it->fi},++it;
++it;
}
if((++it)!=S.end()){
tmp[++tot]=(Node){it->se,it->fi-h[pos]};
if((++it)!=S.end())tmp[++tot]=(Node){it->se,it->fi-h[pos]};
}
sort(tmp+1,tmp+tot+1);
nxtb[pos]=tmp[1].id;
if(tot^1)nxta[pos]=tmp[2].id;
}
for(int i=1;i<=n;++i){
int p1=nxta[i],p2=nxtb[p1];
disa[i][0]=p1?abs(h[p1]-h[i]):0,disb[i][0]=p2?abs(h[p1]-h[p2]):0,st[i][0]=p2;
}
for(int j=1;j<=20;++j)for(int i=1;i<=n;++i){
st[i][j]=st[st[i][j-1]][j-1];
disa[i][j]=disa[i][j-1]+disa[st[i][j-1]][j-1];
disb[i][j]=disb[i][j-1]+disb[st[i][j-1]][j-1];
}
}
inline pii solve(int s,int dis){
pii ret=pii(0,0);
for(int i=20;~i;--i)if(st[s][i]&&disa[s][i]+disb[s][i]<=dis)dis-=disa[s][i]+disb[s][i],ret.fi+=disa[s][i],ret.se+=disb[s][i],s=st[s][i];
if(!nxta[s]||abs(h[nxta[s]]-h[s])>dis)return ret;
return ret.fi+=abs(h[nxta[s]]-h[s]),ret;
}
int main(){
n=read();
for(int i=1;i<=n;++i)h[i]=read();
init(),x0=read();
pii ans;
for(int i=1;i<=n;++i){
pii res=solve(i,x0);
if(!Ans||((long long)ansa*res.se>(long long)ansb*res.fi))ansa=res.fi,ansb=res.se,Ans=i;
}
printf("%d\n",Ans);
for(int i=read(),x,s;i;--i)s=read(),x=read(),ans=solve(s,x),printf("%d %d\n",ans.fi,ans.se);
return 0;
}