题解 P7333【[JRKSJ R1] JFCA】
cyffff
·
·
题解
T1 JFCA
Subtask 1
这个 Subtask 中 n \leqslant 10^3 ,暴力 O(n^2) 向左右拓展即可，但是由于没有 O2，只能通过数据点 1 至 4 数据点（数据点 4 可极限通过），期望得分 20.
Subtask 2
采用捆绑测试，10^5 的数据可以想到要用 O(n\log n) 的算法。
于是我们可以想到二分，但是 a_j 没有单调性。于是我们可以维护区间最大值，满足单调性。
由于题目说这是一个环，我们可以使用分类讨论或者断环为链，这篇题解主要讲断环为链。
我们将每个数存 3 遍，即 a_{i+n+n}=a_{i+n}=a_i.
定义 f(i,j)=\max_{k=i}^j a_k，我们设当前处理的是序号为 i 的数，则 check(x)=\max(f(i-x,i-1),f(i+1,i+x)) 。
我们对于i+n 二分一次即可。
注意事项：
- 1.断环为链时，我们复制 3 遍的原因是处理较后的数时可能会造成数组越界错误。
- 2.我们可以使用 ST表 平衡复杂度到 n\log n，也可以使用其他数据结构如线段树做到 n\log^2 n 的复杂度。
- 3.由于 i\ne j，求区间最大值时不能直接算 f(i-x,i+x)。
接下来就可以愉快的二分了，不理解的和剩余的内容可以结合代码理解。
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+10;
int n,m,st[N][30],lg[N];
namespace IO{
//read(),write()
}using namespace IO;
inline int query(int l,int r){
int q=lg[r-l+1];
return max(st[l][q],st[r-(1<<q)+1][q]);
}
inline int ef(int x,int i){//二分
int l=1,r=n;
while(l<r){
int mid=l+r>>1;
if(max(query(i-mid,i-1),query(i+1,i+mid))>=x){
r=mid;
}else{
l=mid+1;
}
}
return l==n?-1:l;
}
int main(){
n=read();
for(int i=1;i<=n;i++){//断环为链
st[i][0]=st[i+n][0]=st[i+n+n][0]=read();
}
for(int i=2;i<=n+n+n;i++){
lg[i]=lg[i>>1]+1;
}
int ln=lg[n+n+n];
for(int i=1;i<=ln;i++){//ST表预处理
for(int j=1;j+(1<<i)-1<=n+n+n;j++){
st[j][i]=max(st[j][i-1],st[j+(1<<i-1)][i-1]);
}
}
for(int i=1;i<=n;i++){
int b=read();
int a2=ef(b,i+n);
write(a2);
out[len++]=' ';
}
fwrite(out,1,len,stdout);
return 0;
}
```
这道题作为 $T1$ 还是很水的，后面的题就很毒瘤了。
感谢大家参与这场比赛！