题解 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值 ```cpp #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; } ```