CF213E Two Permutations 题解

下文的 \(a+x\) 表示 \(a_1+x,a_2+x,...a_n+x\) 这个序列。

发现 \(n,m\) 不大，所以可以枚举 \(x\)，然后快速判断是否合法。

考虑如何快速判断一个 \(x\) 是否合法。

注意到 \(a,b\) 都是排列。

\(a_1+x,a_2+x,...a_n+x\) 的数在 \([1+x,n+x]\) 范围内。

想象一下，把 \(b\) 中不在 \([1+x,n+x]\) 范围内的数都锁起来不管，只留下 \([1+x,n+x]\) 范围内的数，设这时的 \(b\) 数组中没有被锁的数组成的子序列为 \(b’\)。\(b’\) 和 \(a+x\) 相等，那么这个 \(x\) 就是合法的，这里快速判断两个数组相等显然可以想到哈希。

怎么求 \(b’\) 的哈希值？

从小到大枚举 \(x\)，在上一个 \(x\) 时，\(b’\) 中的数范围为 \([x,n+x-1]\)，所以我们只需要在之前的 \(b’\) 的基础上删去 \(x\) 这个数，然后再加上 \(n+x\) 这个数。

设 \(pos[i]\) 为 \(i\) 在 \(b\) 数组中的位置。
在 \(b\) 数组上的操作就是：锁住 \(b_{pos_{x}}\)，解锁 \(b_{pos_{n+x}}\)

所以，用线段树维护 \(b’\) 的哈希值。仅需要修改操作即可（具体看代码）

怎么快速求出 \(a+x\) 的哈希值？

自己写一下哈希的式子就知道了。具体见代码。

\(Code\):

#include<bits/stdc++.h>
using namespace std;
int read(){
    int x=0;char c=getchar();bool f=0;
    while(c>'9'||c<'0'){f|=(c=='-');c=getchar();}
    while(c<='9'&&c>='0'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
    return f?-x:x;
}
typedef long long ll;
const ll mod=1e9+7;
const ll base=31;
const int MAXN=2e5+5;
int a[MAXN],b[MAXN],pos[MAXN];
int n,m;
#define lch (u<<1)
#define rch (u<<1|1)
ll sum[MAXN<<4],cnt[MAXN<<4];
ll pw[MAXN],S;
void up(int u){
    cnt[u]=cnt[lch]+cnt[rch];
    sum[u]=(sum[lch]*pw[cnt[rch]]%mod+sum[rch])%mod;
}
void add(int u,int l,int r,int p,int val){
    if(l==r){
        cnt[u]+=val;
        sum[u]=cnt[u]*b[p]%mod;
        return;
    }
    int mid=l+r>>1;
    if(p<=mid)   add(lch,l,mid,p,val);
    else    add(rch,mid+1,r,p,val);
    up(u);
}
int main(){
    n=read(),m=read();
    ll A=0;pw[0]=1ll;ll S=0;
    for(int i=1;i<=n;i++){
        a[i]=read();
        A=(A*base%mod+a[i])%mod;
        pw[i]=pw[i-1]*base%mod;
        S=(S+pw[i-1])%mod;
    }
    for(int i=1;i<=m;i++){b[i]=read();pos[b[i]]=i;}
    int ans=0;
    //初始所有数都被锁住
    for(int i=1;i<=m;i++){//b数组中出现 [i-n+1,i]
        add(1,1,m,pos[i],1);//解锁 i
        if(i>n) add(1,1,m,pos[i-n],-1);//锁住 i-n
        if(i>=n){
            int x=i-n;
            ll C=(A+x*S%mod)%mod,B=sum[1];//C就是a+x的hash值
            if(C==B)    ans++;
        }
    }
    printf("%d",ans);
    return 0;
}