题解：P10833 [COTS 2023] 下 Niz

· · 题解

发现当区间最大值确定下来时，区间的长度就固定了，于是以最值位置为分治中心，枚举较短区间的相应端点，区间就确定下来了，问题就变为判断一个区间是否为 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;
}