自动搬运

查看原文

来自洛谷，原作者为

	Zelensky 人们心中的成见是一座大山

搬运于2025-08-24 23:01:40，当前版本为作者最后更新于2025-07-16 21:11:57，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

发现当区间最大值确定下来时，区间的长度就固定了，于是以最值位置为分治中心，枚举较短区间的相应端点，区间就确定下来了，问题就变为判断一个区间是否为 $1$ 到 $n$ 的排列。

这是一个经典问题，我们维护一个 $las$ 数组，维护每个位置上的数上一次出现的位置，当区间内的某个位置的 $las$ 也在区间内时，这个区间显然不合法。

我们使用线段树或 ST 表维护区间 $las$ 的最大值，判断它与左端点的关系，即可快速判断区间是否为排列。

时间复杂度 $O(n\log n)$ 。

#include<bits/stdc++.h>
using namespace std;
int n,a[(int)1.1e6],ans;
struct ST{
	int f[(int)1.1e6][30],lg[(int)1.1e6];
	void build(int n){
		lg[1]=0;
		for(int i=2;i<=n;i++)lg[i]=lg[i>>1]+1,f[i][0]=i;
		f[1][0]=1;
		for(int i=1;(1<<i)<=n;i++){
			for(int j=1;j+(1<<i)-1<=n;j++){
				int lp=f[j][i-1],rp=f[j+(1<<(i-1))][i-1];
				f[j][i]=(a[lp]>a[rp]?lp:rp);
			}
		}	
	}
	int query(int l,int r){
		int k=lg[r-l+1],lp=f[l][k],rp=f[r-(1<<k)+1][k];
		return a[lp]>a[rp]?lp:rp;
	}
}s;
int nw[(int)1.1e6],las[(int)1.1e6];
struct SEG{
	int f[(int)1.1e6][30],lg[(int)1.1e6];
	void build(int n){
		lg[1]=0;
		for(int i=2;i<=n;i++)lg[i]=lg[i>>1]+1,f[i][0]=i;
		f[1][0]=1;
		for(int i=1;(1<<i)<=n;i++){
			for(int j=1;j+(1<<i)-1<=n;j++){
				int lp=f[j][i-1],rp=f[j+(1<<(i-1))][i-1];
				f[j][i]=(las[lp]>las[rp]?lp:rp);
			}
		}	
	}
	int query(int l,int r){
		int k=lg[r-l+1],lp=f[l][k],rp=f[r-(1<<k)+1][k];
		return max(las[lp],las[rp]);
	}
}T;
void solve(int l,int r){
	if(l>r)return ;if(l==r)return ans+=a[l]==1,void();
	int mid=s.query(l,r),len=a[mid];solve(l,mid-1),solve(mid+1,r);
	if(mid-l<=r-mid){
		for(int i=l;i<=mid;i++){
			int R=i+len-1;
			if(R<mid)continue;if(R>r)return ;
			ans+=(T.query(i,R)<i);
		}
	}
	else {
		for(int i=r;i>=mid;i--){
			int L=i-len+1;
			if(L>mid)continue;if(L<l)return ;
			ans+=(T.query(L,i)<L);
		}
	}
}
int rt;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		las[i]=nw[a[i]];
		nw[a[i]]=i;
	}
	s.build(n),T.build(n),solve(1,n);
	cout<<ans<<endl;
	return 0;
}