自动搬运

查看原文

来自洛谷，原作者为

	cyffff Not yet for the story on the last page, it's not the end.

搬运于2025-08-24 22:28:52，当前版本为作者最后更新于2021-01-14 17:26:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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)$。

接下来就可以愉快的二分了，不理解的和剩余的内容可以结合代码理解。

$std$:

#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$ 还是很水的，后面的题就很毒瘤了。

感谢大家参与这场比赛！