题解 CF213E 【Two Permutations】

· · 题解

因为我们要比较区间，所以先将a排列 hash
注意，因为a是一个排列，所以它里面的元素一定是从1~n的，所以，我们可以使pos[b[i]] = i，然后判断pos[i-n+1]~pos[i]和a排列是否符合要求
这里的符合要求包括：

  1. pos[i-n+1]~pos[i]减去x等于a排列
  2. b[pos[i-n+1]]~b[pos[i]]是b的子序列

而这两个要求都可以通过计算b[pos[i-n+1]]~b[pos[i]]在原排列里构成的子序列的hash值来判断
之后我们要做的就是快速的求出b[pos[i-n+1]]~b[pos[i]]在原排列b中构成的子序列的hash值
因为b_i并不连续，用线段树维护hash值 

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ULL unsigned long long
#define ls (p << 1)
#define rs (p << 1 | 1)
#define mid ((l + r) >> 1)
using namespace std;
int read() {
    int k = 0, f = 1; char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9')
      k = k * 10 + c - 48, c = getchar();
    return k * f;
}
int a[200010], b[200010], pos[200010], ans;
ULL hasha, qpow[200010] = {1}, sum;
struct zzz{
    ULL a, tot;
}tree[200010 << 2];
void up(int l, int r, int p) {
    tree[p].tot = tree[ls].tot + tree[rs].tot;
    tree[p].a = tree[ls].a * qpow[tree[rs].tot] + tree[rs].a;
}
void update(int l, int r, int pos, int p, int k) {
    if(l == r) {
        if(!k) tree[p].tot -= 1;
        else tree[p].tot += 1;
        tree[p].a = k; return ;
    }
    if(pos <= mid) update(l, mid, pos, ls, k);
    if(pos > mid) update(mid+1, r, pos, rs, k);
    up(l, r, p);
}
int main() {
    int n = read(), m =read();
    for(int i = 1; i <= n; ++i) {
        a[i] = read(), hasha = hasha * 23 + a[i];
        qpow[i] = qpow[i-1] * 23;
        sum += qpow[i-1];
    }
    for(int i = 1; i <= m; ++i) b[i] = read(), pos[b[i]] = i;
    for(int i = 1; i <= m; ++i) {
        if(i > n) update(1, m, pos[i-n], 1, 0);
        update(1, m, pos[i], 1, i);
        int d = i - n;
        if(d >= 0 && tree[1].a == d*sum+hasha) ++ans;
    }
    printf("%d", ans);
    return 0;
}