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;
}