「Codeforces 213E」Two Permutations【哈希 + 线段树】

Description

给定长为 nn 的排列 AA 和长为 mm 的排列 BB。求所有的 dd 值,使得:

  • 定义长度为 nn 的序列 Ci=Ai+dC_i = A_i + d
  • 序列 CC 是序列 BB子序列

求有多少个符合条件的 dd 值。

Input

第一行包含两个整数 nnmm (1nm200000)(1 \leqslant n \leqslant m \leqslant 200000),表示排列的长度。

第二行包含 nn 个不同的整数,表示排列 AA。第三行包含 mm 个不同的整数,表示排列 BB

Output

输出一行,表示问题的答案。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Sample Input #1:
1 1
1
1

Sample Input #2:
1 2
1
2 1

Sample Input #3:
3 3
2 3 1
1 2 3

Sample Output

1
2
3
4
5
6
7
8
Sample Output #1:
1

Sample Output #2:
2

Sample Output #3:
0

Solution

根据 BB 构造 CC,使得 CBi=iC_{B_i} = i。那么从 d+1d + 1d+nd + n,就对应了 CC 中的一段连续区间。

枚举 dd,用线段树维护哈希值即可。时间复杂度为 O(nlogn)O(n \log n)

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
#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;
const int maxn = 200010, p = 43;
int n, m, ans, a[maxn], cnt[maxn << 2];
ull h, sum, base[maxn], node[maxn << 2];

void modify(int k, int l, int r, int p, int v) {
if (l == r) { cnt[k] = !!(node[k] = v); return; }
int mid = (l + r) >> 1;
mid >= p ? modify(k << 1, l, mid, p, v) : modify(k << 1 | 1, mid + 1, r, p, v);
cnt[k] = cnt[k << 1] + cnt[k << 1 | 1];
node[k] = node[k << 1] + node[k << 1 | 1] * base[cnt[k << 1]];
}

int main() {
scanf("%d %d", &n, &m), base[0] = 1;
for (int i = 1; i <= n; i++) {
base[i] = base[i - 1] * p;
}
for (int i = 0, x; i < n; i++) {
scanf("%d", &x), h += x * base[i], sum += base[i];
}
for (int i = 0, x; i < m; i++) {
scanf("%d", &x), a[x - 1] = i;
}
for (int i = 0; i < n; i++) {
modify(1, 0, m - 1, a[i], i + 1);
}
ans = (node[1] == h);
for (int i = n; i < m; i++) {
modify(1, 0, m - 1, a[i - n], 0), modify(1, 0, m - 1, a[i], i + 1);
ans += (node[1] == h + (i - n + 1) * sum);
}
printf("%d\n", ans);
return 0;
}