【Codeforces 1175F】The Number of Subpermutations | Mrsrz's blog

随机权值。

题目大意：

给定一个数列 $a_1,a_2,a_3,\ldots,a_n$，求有多少个子区间，满足以下条件：

• 设区间长度为 $m$，则该子区间中 $1\sim m$ 都恰好出现一次。

题解：

我们给 $1\sim n$ 的每个数赋一个随机权值，然后一个区间的权值为区间内所有元素权值的异或和。那么对于每个 $i$，$1\sim i$ 这些数就对应一个权值。用 $64$ 位整数随机，冲突的概率非常小。

这样对于满足条件的连续区间，我们只需要看它的权值即可，和顺序就无关了。

由于区间肯定会包含 $1$，所以我们枚举每个 $1$ 的位置，然后考虑包含这个 $1$ 的区间的情况。

一个长度为 $m$ 的区间的最大值为 $m$，我们考虑最大值在这个区间右边的情况。

从 $1$ 开始向右扫描，并维护最大值 $mx$ 以及权值异或和。然后如果目前已经有 $k$ 个数了，则只需要考察当前的异或和再异或上这个 $1$ 左边 $(mx−k)$ 个数的异或和，是否等于长度为 $m$ 的区间的权值就好了。

所以先预处理 $1$ 左边的数的后缀异或和，然后向右扫描就好了。

对于最大值在左边的也同样处理。

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

Code：

#include<cstdio>
#include<ctime>
#include<random>
#include<algorithm>
using namespace std;
typedef unsigned long long uLL;
mt19937_64 mt(time(0));
const int N=4e5;
int A[N],n;
uLL rd[N],pr[N],ans,xL[N];
void solve(){
    for(int i=1;i<=n;++i)if(A[i]==1){
        int j;
        for(j=i-1;A[j]!=1;--j)xL[i-j]=xL[i-j-1]^rd[A[j]];
        int mx=1,len=i-j-1;uLL nw=rd[1];
        for(j=i+1;A[j]!=1;++j){
            mx=max(mx,A[j]),nw^=rd[A[j]];
            if(mx>=j-i+1&&mx<=j-i+1+len&&pr[mx]==(nw^xL[mx-(j-i+1)]))++ans;
        }
    }
}
int main(){
    scanf("%d",&n),A[0]=A[n+1]=1;
    for(int i=1;i<=n;++i)scanf("%d",A+i),rd[i]=mt(),pr[i]=pr[i-1]^rd[i],ans+=A[i]==1;
    solve(),reverse(A+1,A+n+1),solve();
    printf("%llu\n",ans);
    return 0;
}