传送门
problem
数据范围：
1
≤
n
≤
1
0
5
1≤n≤10^5
1≤n≤105，
1
≤
m
≤
1
0
4
1≤m≤10^4
1≤m≤104。
solution
感觉这道题挺妙的。
首先要解决的一个问题是，怎么找到题目中定义的最近城市和次近城市？
一个思路就是从
n
∼
1
n\sim 1
n∼1 倒着扫，处理到
i
i
i 时，我们想知道
[
i
+
1
,
n
]
[i+1, n]
[i+1,n] 中，
h
i
h_i
hi 的前驱，后继，前驱的前驱，后继的后继，因为只最近和次近肯定在这
4
4
4 个点中，排序判一下具体是哪两个即可。
由于我们要支持插入，查询前驱后继这些操作，可以很方便地用 set 维护。
接下来就是询问了。两种询问实质上是一样的，因为第一个询问可以通过枚举每一个点转换成第二个询问。
暴力的做法就是直接模拟，先走一步 A，然后走 B，再走 A，
⋯
\cdots
⋯，直到不能走为止。
怎么优化这个暴力呢，不妨考虑倍增。记 A,B 各走一次为一轮，暴力跳看能走几轮，最后特判一下 A 是否可以再走一次即可。
时间复杂度
O
(
n
log
n
)
O(n\log n)
O(nlogn)。
PS：代码中倍增是以
1
1
1 为下标的，
0
0
0 记的是 A 跳一次的信息。
code
#include<bits/stdc++.h>
#define ll long long
using namespace std
;
namespace IO
{
const int Rlen
=1<<22|1;
char buf
[Rlen
],*p1
,*p2
;
inline char gc(){
return (p1
==p2
)&&(p2
=(p1
=buf
)+fread(buf
,1,Rlen
,stdin),p1
==p2
)?EOF:*p1
++;
}
template<typename T
>
inline T
Read(){
char c
=gc();T x
=0,f
=1;
while(!isdigit(c
)) f
^=(c
=='-'),c
=gc();
while( isdigit(c
)) x
=(x
+(x
<<2)<<1)+(c
^48),c
=gc();
return f
?x
:-x
;
}
inline int in() {return Read
<int>();}
}
using IO
::in
;
const int N
=1e5+5;
int n
,m
,pos
,X0
,h
[N
];
ll disA
[N
],disB
[N
],posA
[N
],posB
[N
],inf
=1e15;
ll p
[N
][21],A
[N
][21],B
[N
][21];
set
<ll
>S
;
unordered_map
<ll
,int>Map
;
struct node
{ll h
,dis
;}tmp
[5];
bool operator<(const node
&p
,const node
&q
) {return (p
.dis
==q
.dis
)?p
.h
<q
.h
:p
.dis
<q
.dis
;}
ll
Abs(ll x
) {return x
>0?x
:-x
;}
void prework(){
S
.insert(inf
),S
.insert(inf
-1),S
.insert(-inf
),S
.insert(-inf
+1);
for(int i
=n
;i
>=1;--i
){
S
.insert(h
[i
]);
tmp
[1].h
=*--S
.lower_bound(h
[i
]);
tmp
[2].h
=*--S
.lower_bound(tmp
[1].h
);
tmp
[3].h
=*S
.upper_bound(h
[i
]);
tmp
[4].h
=*S
.upper_bound(tmp
[3].h
);
for(int j
=1;j
<=4;++j
) tmp
[j
].dis
=Abs(tmp
[j
].h
-h
[i
]);
sort(tmp
+1,tmp
+5);
disA
[i
]=tmp
[2].dis
,posA
[i
]=Map
[tmp
[2].h
];
disB
[i
]=tmp
[1].dis
,posB
[i
]=Map
[tmp
[1].h
];
if(posA
[i
]) A
[i
][0]=disA
[i
],p
[i
][0]=posA
[i
];
if(posB
[posA
[i
]]) A
[i
][1]=disA
[i
],B
[i
][1]=disB
[posA
[i
]],p
[i
][1]=posB
[posA
[i
]];
for(int j
=2;j
<=20;++j
){
p
[i
][j
]=p
[p
[i
][j
-1]][j
-1];
A
[i
][j
]=A
[i
][j
-1]+A
[p
[i
][j
-1]][j
-1];
B
[i
][j
]=B
[i
][j
-1]+B
[p
[i
][j
-1]][j
-1];
}
}
}
void calc(int S
,int X
,ll
&ansA
,ll
&ansB
){
ansA
=ansB
=0;
for(int i
=20;i
>=1;--i
){
if(p
[S
][i
]&&ansA
+ansB
+A
[S
][i
]+B
[S
][i
]<=X
){
ansA
+=A
[S
][i
];
ansB
+=B
[S
][i
];
S
=p
[S
][i
];
}
}
if(p
[S
][0]&&ansA
+ansB
+A
[S
][0]<=X
) ansA
+=A
[S
][0];
}
ll ansA
,ansB
;
int main(){
n
=in();
for(int i
=1;i
<=n
;++i
) h
[i
]=in(),Map
[h
[i
]]=i
;
prework(),X0
=in(),m
=in();
double Min
=1e18;
for(int i
=1;i
<=n
;++i
){
calc(i
,X0
,ansA
,ansB
);
double now
=ansB
?1.0*ansA
/ansB
:1e18;
if(Min
>now
) Min
=now
,pos
=i
;
}
printf("%d\n",pos
);
while(m
--){
int S
=in(),X
=in();
calc(S
,X
,ansA
,ansB
),printf("%lld %lld\n",ansA
,ansB
);
}
return 0;
}
