首先数据范围是 \(2\mathrm{e}5\)，支持枚举，问题留给了判断子序列。不简单想到了哈希，一开始想到的是树状数组，发现树状数组比较菜，就转向了线段树。
一开始先把 \(b\) 中的 \(1\sim n\) 加到线段树里，然后不断的删除最小的，加入最大的，这个过程只需要单点修改，不需要建树，也不需要 pushdown，线段树的每个节点维护出现的有效数字个数和这个区间的哈希值即可。
对于枚举的 \(a\) 的哈希值，还需要维护一个 \(base\) 的前缀和。每次统计答案直接判断 \(a\) 的哈希值和线段树维护的哈希值是否相等即可。
\(base\) 取个质数就行，模数要注意一下。
代码实现较为简单，个人感觉有点难想。
#include <bits/stdc++.h>
#define int long long
const int N(200005), Base(13331), Mod(998244853);
inline int read() {
int f(1), x(0);
char c = getchar();
for (; !isdigit(c); c = getchar()) if (c == '-') f = -1;
for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c & 15);
return f * x;
}
int n, m, a[N], b[N], bs[N], sbs[N], hsa, rnk[N], ans;
namespace SegmentTree {
#define lid p << 1
#define rid p << 1 | 1
struct Tree {
int hsh, cnt;
} t[N << 2];
inline void pushup(int p) {
t[p].cnt = t[lid].cnt + t[rid].cnt;
t[p].hsh = (t[lid].hsh * bs[t[rid].cnt] % Mod + t[rid].hsh) % Mod;
}
void update(int p, int pl, int pr, int x, int v) {
if (pl == pr) {
t[p].hsh = v;
t[p].cnt = (v > 0) ? 1 : 0;
return;
}
int mid = (pl + pr) >> 1;
if (x <= mid) update(lid, pl, mid, x, v);
else update(rid, mid + 1, pr, x, v);
pushup(p);
}
#undef lid
#undef rid
} using namespace SegmentTree;
signed main() {
bs[0] = sbs[0] = 1;
for (int i = 1; i <= 200000; ++i) bs[i] = bs[i - 1] * Base % Mod;
for (int i = 1; i <= 200000; ++i) sbs[i] = (sbs[i - 1] + bs[i]) % Mod;
n = read(), m = read();
for (int i = 1; i <= n; ++i) {
a[i] = read();
hsa = (hsa * bs[1] % Mod + a[i]) % Mod;
}
for (int i = 1; i <= m; ++i) {
b[i] = read();
rnk[b[i]] = i;
if (b[i] <= n) update(1, 1, m, rnk[b[i]], b[i]);
}
ans += (hsa == t[1].hsh);
for (int i = n + 1; i <= m; ++i) {
int j = i - n;
update(1, 1, m, rnk[j], 0);
update(1, 1, m, rnk[i], i);
hsa = (hsa + sbs[n - 1]) % Mod;
ans += (hsa == t[1].hsh);
}
printf("%lld\n", ans);
}