自动搬运

查看原文

来自洛谷，原作者为

	Rigel 苍山负雪，明烛天南。|| 高二现役 OIer。

搬运于2025-08-24 23:02:10，当前版本为作者最后更新于2024-08-18 09:08:15，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

思路

在一个排序后为等差数列的数列中，定义 $l$ 为数列长度，$d$ 为可能的数列公差。

试分析以 $i$ 为断点形成的 $2$ 个排序后为等差数列的数列中 $d$ 与 $l$ 的关系。

先定义 $l$ 为“特殊的”，当且仅当 $l=\begin{cases} \lfloor\frac{n}{2}\rfloor\ 或\ \lfloor\frac{n}{2}\rfloor+1&n=2x+1,\ x\in\mathbb{N+},\\ \frac{n}{2}&n=2x,\ x\in\mathbb{N+}. \end{cases}$

存在如下 $3$ 种情况：

• 当 $l \in [1,2]$ 时，$d \in [1,n-1]$。

• 当 $l \in [3,n]$ 时，$d=\begin{cases} 1\ 或\ 2& l\ 为“特殊的”,\\ 1 & \mathop{\operatorname{otherwise}}.\\ \end{cases}$

再定义 $\mathop{f_i}\limits_{i \in [1,n]}=[\ [p_1,p_2,\cdots,p_i] 为等差数列]$，$\mathop{g_i}\limits_{i \in [1,n]}=[\ [p_{i},p_{i+1},\cdots,p_n]为等差数列]$。

注意到，$\forall i\in [1,n)$，$f_i=1\ \land \ g_{i+1}=1$，则 $i$ 合法，因此求出 $f_i$ 与 $g_i$ 即可。

下面以求出 $f_i$ 为例，此时 $l=i$。

正难则反，我们设出 $d$ 的值并检验 $d$ 的合法性，若 $d$ 合法，则 $f_i=1$。

显然，$l \le 2$ 时 $f_i=1$，不再赘述。

当 $l > 2$ 时，

• 先设 $d=1$。若 $l=\mathop{\operatorname{max}}(p_1,p_2,\cdots,p_i)-\mathop{\operatorname{min}}(p_1,p_2,\cdots,p_i)+1$，则 $d$ 合法。

• 若 $l$ 为“特殊的”，再设 $d=2$，此时遍历数列 $[p_1,p_2,\cdots,p_i]$ 判断 $d$ 的合法性（详情见代码）。

不难发现，求 $f_i$ 的过程中，“遍历数列”的操作至多进行 $2$ 次，不会爆时间。

求 $g_i$ 时，$l=n-i+1$，过程同理，注意顺序。

代码

#include<bits/stdc++.h>
#define int long long
#define INF 0x7fffffffffffffff
#define _max(a,b) ((a)>(b)?(a):(b))
#define _min(a,b) ((a)<(b)?(a):(b))
#define maxn 2000010
using namespace std;
int t,n,a[maxn],vis[maxn],f[maxn],g[maxn],ans;
inline int read(){
	int ret=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')ret=ret*10+(ch&15),ch=getchar();
	return ret*f;
}
signed main(){
	t=read();
	while(t--){
		n=read(),ans=0;
		for(int i=1;i<=n;i++)a[i]=read(),vis[i]=0;
		if(n==1){printf("0\n");continue;}
		//求 f[i] 
		int cnt=0,minn=INF,mx=-INF;
		for(int i=1;i<=n;i++){
			vis[a[i]]=1;
			if(a[i]>=mx)mx=a[i];
			if(a[i]<=minn)minn=a[i];
			if(mx-minn+1==i||i<=2){f[i]=1;continue;}	
			if(((n&1)&&(i==(n>>1)||i==(n>>1)+1))||(!(n&1)&&(i==(n>>1)))){
				int k=((mx-minn)>>1)+1;
				if(k!=i){f[i]=0;continue;}
				int op=0;
				for(int j=minn;j<=mx;j+=2)if(!vis[j]){op=1;break;}
				f[i]=op^1;
			}else f[i]=0;
		}
		//求 g[i] 
		cnt=0,minn=INF,mx=-INF;
		for(int i=1;i<=n;i++)vis[i]=0;		
		for(int i=n;i>=1;i--){
			vis[a[i]]=1;
			if(a[i]>=mx)mx=a[i];
			if(a[i]<=minn)minn=a[i];
			if(mx-minn+1==(n-i+1)||(n-i+1)<=2){g[i]=1;continue;}	
			if(((n&1)&&((n-i+1)==(n>>1)||(n-i+1)==(n>>1)+1))||(!(n&1)&&(n-i+1)==(n>>1))){
				int k=((mx-minn)>>1)+1;
				if(k!=(n-i+1)){g[i]=0;continue;}
				int op=0;
				for(int j=minn;j<=mx;j+=2)if(!vis[j]){op=1;break;}
				g[i]=op^1;
			}else g[i]=0;
		}
		for(int i=1;i<=n-1;i++)if(f[i]&&g[i+1])ans++;
		printf("%lld\n",ans);
	}
	return 0;
}