CF213E Two Permutations 题解
题意：
给出两个排列$a,b $，长度分别为 \(n,m\)，你需要计算有多少个 $ x $，使得 \(a_1 + x,a_2 + x,...a_n + x\) 是 \(b\) 的子序列。
\(n \leq m \leq 2 \times 10^5\)
分析：
一个很自然的思路是直接枚举 \(x\)，然后只保留 \(b\) 中值域在 \([x+1,x+n]\) 的数，然后利用哈希判断 \(a\) 与 \(b\) 是否相同。
显然是可行的，看看如何维护 \(a\) 与 \(b\) 的哈希值。
维护 \(a\) 的哈希值是简单的，记 \(S = \sum_{i=1}^{n}a_i \times base^{n-i+1}\)，显然
\[\sum_{i=1}^{n}(a_i+x) \times base^{n-i+1}=S+x\sum_{i=1}^{n}base^{n-i+1} \]\(b\) 的哈希也不难，考虑保留值域从 \([l,r]\) 到 \([l+1,r+1]\) 的过程，明显删掉了 \(l\)，加上了 \(r\)。
我们可以利用线段树动态维护每个点的 \(b_i \times base^{n-i+1}\)，删掉一个数后前面的数都要除以 \(base\)，加入一个数后前面的数都要乘上 \(base\)。
在线段树里面维护两个值 \(c_1,c_2\) 分别记录这个区间的 \(\sum b_i \times base^{n-i+1}\) 和里面有值的数的数量。
这个线段树需要支持区间乘、单点赋值、区间查询。
时间复杂度为 \(O(n \log n)\)。
代码：
#include<bits/stdc++.h>
#define int long long
#define base 1000000007
#define mod 998244353
#define N 200005
using namespace std;
int read() {
char ch = getchar(); int x = 0, f = 1;
while(ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar(); }
while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
return x * f;
}
void write(int x) {
if(x < 0) putchar('-'), x = -x;
if(x > 9) write(x / 10);
putchar('0' + x % 10);
}
int Pow(int a, int n) {
if(n == 0) return 1;
if(n == 1) return a % mod;
int x = Pow(a, n / 2);
if(n % 2 == 0) return x * x % mod;
else return x * x % mod * a % mod;
}
int inv(int x) {
return Pow(x, mod - 2);
}
int n, m, hx, ans;
int a[N], b[N], h[N], f[N], S;
int c1[N * 4], c2[N * 4], tag[N * 4]; //c1记录hash值,c2记录有值的个数
void pushup(int u) {
c1[u] = (c1[u * 2] + c1[u * 2 + 1]) % mod;
c2[u] = c2[u * 2] + c2[u * 2 + 1];
}
void maketag(int u, int x) {
if(tag[u] != -1) tag[u] = tag[u] * x % mod;
else tag[u] = x % mod;
if(c1[u] != -1) c1[u] = c1[u] * x % mod;
else c1[u] = x % mod;
}
void pushdown(int u) {
if(tag[u] == -1) return;
maketag(u * 2, tag[u]);
maketag(u * 2 + 1, tag[u]);
tag[u] = -1;
}
void update1(int u, int L, int R, int x, int y) { //c1[x]=y
if(L == R) {
if(c1[u] != 0 && y == 0) c2[u] = 0;
else if(c1[u] == 0 && y != 0) c2[u] = 1;
c1[u] = y;
return;
}
int mid = (L + R) / 2;
pushdown(u);
if(x <= mid) update1(u * 2, L, mid, x, y);
else update1(u * 2 + 1, mid + 1, R, x, y);
pushup(u);
}
void update2(int u, int L, int R, int l, int r, int x) { //c1[l...r]乘上x
if(r < L || R < l) return;
if(l <= L && R <= r) {
maketag(u, x);
return;
}
pushdown(u);
int mid = (L + R) / 2;
update2(u * 2, L, mid, l, r, x);
update2(u * 2 + 1, mid + 1, R, l, r, x);
pushup(u);
}
int query(int u, int L, int R, int l, int r) { //查询[l,r]的c2
if(r < L || R < l) return 0;
if(l <= L && R <= r) return c2[u];
pushdown(u);
int mid = (L + R) / 2;
return query(u * 2, L, mid, l, r) + query(u * 2 + 1, mid + 1, R, l, r);
}
void Insert(int x, int y) { //在x处插入y
int z = query(1, 1, m, x + 1, m);
update1(1, 1, m, x, y * h[z] % mod);
update2(1, 1, m, 1, x - 1, base);
}
void Delete(int x) {
update1(1, 1, m, x, 0);
update2(1, 1, m, 1, x - 1, inv(base) % mod);
}
signed main() {
memset(tag, -1, sizeof(tag));
n = read(), m = read();
for(int i = 1; i <= n; i++) a[i] = read();
for(int i = 1; i <= m; i++) b[i] = read(), f[b[i]] = i;
h[0] = 1;
for(int i = 1; i <= 200000; i++) h[i] = h[i - 1] * base % mod;
for(int i = 1; i <= n; i++) {
S += h[n - i]; S %= mod;
hx += a[i] * h[n - i] % mod; hx %= mod;
}
for(int i = 1; i <= n; i++) Insert(f[i], b[f[i]]);
for(int x = 0; x <= m - n; x++) { //保留b值域为 [1+x, x+n] 的数
if(x) {
hx += S % mod; hx %= mod;
Delete(f[x]);
Insert(f[x + n], b[f[x + n]]);
}
if(c1[1] == hx) ans++;
}
write(ans);
return 0;
}