线段树维护序列哈希。

CF213E

题意

给出两个排列 a,ba,b，长度分别为 n,mn,m，你需要计算有多少个 xx，使得 a1+x,a2+x,…,an+xa_1 + x,a_2 + x,\dots,a_n + x 是 bb 的子序列，n≤m≤2×105n \le m \le 2 \times 10^5。

题解

枚举 xx，由于 aia_i 是排列，此时对应 aa 的值域为 [1+x,n+x][1+x,n+x]，此时我们只需要将 bib_i 中在这个值域内的数提取出来（不改变顺序），判断与 a1+x,a2+x,…,an+xa_1+x,a_2+x,\dots,a_n+x 是否相同即可。

考虑序列相同这里用到序列哈希，对于 a1,a2,…,ana_1,a_2,\dots,a_n，先预处理其哈希值 ff，那么 a1+x,a2+x,…,an+xa_1+x,a_2+x,\dots,a_n+x 哈希值为 f+x×∑i=0nbif+x\times \sum_{i=0}^n b^{i}（bb 为底数），对于 bb，枚举 xx 时会在某种位置 删除/加入 一个数，用 线段树/平衡树 维护序列哈希即可。

CODE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <bits/stdc++.h>
#define fi first
#define se second
#define ls (x<<1)
#define rs (x<<1|1)
#define mid ((l+r)>>1)
using namespace std;
typedef long long ll;
const int N = 200010;
typedef pair<ll,ll> pll;
const int p1 = 1019260817; // 双模 hash 
const int p2 = 1019260819;
// const int bs = 125641; // 基数
const int bs = 1000;
pll operator*(const pll &a,const ll &b) {return pll(a.fi * b % p1, a.se * b % p2);}
pll operator*(const pll &a,const pll &b) {return pll(a.fi * b.fi % p1, a.se * b.se % p2);}
pll operator+(const pll &a,const ll &b) {return pll((a.fi + b) % p1, (a.se + b) % p2);}
pll operator-(const pll &a,const pll &b) {return pll((a.fi - b.fi + p1) % p1, (a.se - b.se + p2) % p2);}
pll operator+(const pll &a,const pll &b) {return pll((a.fi + b.fi) % p1, (a.se + b.se) % p2);}
pll pw[N], pws[N]; // pw[i] = bs ^ i, pws[i] = \sum_{j=0}^i bs^j
void init(int n) {
    pw[0] = pws[0] = {1, 1};
    for (int i = 1; i <= n; ++i) pw[i] = pw[i - 1] * bs, pws[i] = pws[i - 1] + pw[i];
}
struct dat {
    pll f; // 哈希值
    int len; // 串长
    dat() { f = {0, 0}; len = 0; }
    dat(const pll &_f,const int &_len) { f = _f; len = _len; }
};
dat operator*(const dat &a,const dat &b) { // hash 值拼接
    return dat(a.f * pw[b.len] + b.f, a.len + b.len);
}
ostream &operator<<(ostream &out,const dat &a) {
    return out<<"dat{ ("<<a.f.first<<", "<<a.f.second<<"), l="<<a.len<<" } ";
}

int a[N],b[N],p[N],n,m;
dat D[N<<2];
void pushup(int x) {D[x]=D[ls]*D[rs];}
void modify(int ps,int vl,int l=1,int r=m,int x=1) {
    if(l==r) {
        if(vl==-1) D[x]=dat();
        else D[x]=dat(pll(vl,vl),1);
        return ;
    }
    if(ps<=mid) modify(ps,vl,l,mid,ls);
    else modify(ps,vl,mid+1,r,rs);
    pushup(x);
}

int main() {
    scanf("%d%d",&n,&m);
    init(m); dat Ha;
    for(int i=1;i<=n;++i) scanf("%d",&a[i]),Ha=Ha*dat(pll(a[i],a[i]),1);
    for(int i=1;i<=m;++i) scanf("%d",&b[i]),p[b[i]]=i;
    for(int i=1;i<n;++i) modify(p[i],b[p[i]]);
    // cerr<<Ha<<endl;
    int ans=0;
    for(int x=0;n+x<=m;++x) {
        modify(p[n+x],b[p[n+x]]);
        if(x>0) modify(p[x],-1);
        // cerr<<"x="<<x<<" "<<D[1]<<endl;
        if(D[1].f==(Ha.f+pws[n-1]*x)) ++ans;
    }
    printf("%d\n",ans);
    return 0;
}