【题目描述】
对于整数序列 ((a_1,a_2,a_3,cdots,a_n)) 和 (1 sim n) 的排列 ((p_1,p_2,p_3,cdots,p_n))，称 ((a_1,a_2,a_3,cdots,a_n)) 符合 ((p_1,p_2,p_3,cdots,p_n))，当且仅当
- $a$中任意两个数字互不相同
- 将$a$ 从小到大排序后，将会得到 $(a_{p_1},a_{p_2},a_{p_3},cdots,a_{p_n})$ 。 现在给出 $1 cdots n$ 的排列 ${p}$ 和序列 ${h}$，求出哪些 ${h}$ 的子串符合排列 ${p}$。
【输入格式】
第一行两个空格隔开的正整数 (n,m)。
第二行 (n) 个空格隔开的正整数，表示排列 (p)。
第三行 (m) 个空格隔开的正整数，表示序列 (h)。
【输出格式】
第一行一个整数 (k)，表示符合 {p}{p} 的子串个数。
第二行 (k) 个空格隔开的正整数，表示这些子串的起始位置（编号从 (1) 开始）。请将这些位置按照从小到大的顺序输出。特别地，若 (k=0)，那么你也应当输出一个空行。
虽然说看起来不像 但是这题是个KMP匹配
注意到 对于一个数组(a_{1 sim n})，其中(a_i)表示第(i)个数在(n)个数中的相对大小是第(a_i)大，假设另一个数组(cnt_{1 sim n}) 表示第(i)个数前面有(cnt_i)个数比它大，那么这样的一个(cnt)数组和(a)数组是一一对应的。以样例(2,1,4,5,3)为例 对应的(cnt)数组是(0,0,2,3,2)
于是 我们把原题转变为了求 ({h})中的一段长为(n)的子串 对应的(cnt)数组 和 排列({p})对应的(cnt)数组相等
这里直接暴力枚举是(O(nm))的 肯定会炸
所以考虑用KMP的思想 令(nxt[i])表示排列({p})中最长的 前缀的(cnt)数组和后缀的(cnt)数组相同 的长度(类似KMP)
求法就和KMP差不多 具体见代码
主要是如何快速求出(cnt)数组呢？这个用树状数组或线段树就能很容易的实现 每次在 当前数的值 的位置单点修改+1(即上文第二段的(a_i)) 然后查询(1 sim a_i-1)的和
以样例为例 (2,1,4,5,3)
第一次让位置2 ++ 然后查询(1 sim 1) 得到0
第二次让位置1 ++ 查询(1 sim 0) 得到0
第三次让位置4 ++ 查询(1 sim 3) 得到2
以此类推
注意题目中的({h})序列需要离散化处理一下 剩下的就是和KMP差不多的匹配了 注意每次失配时把失配扔掉的那些元素在树状数组上-1
代码
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#define lowbit(x) x&(-(x))
using namespace std;
int n, m, sz;
int q[1000010], h[1000010], srt[1000010], cnt[1000010];
int tr[1000010];
int nxt[1000010];
int ans[1000010];
void updata(int ind, int x) {
while (ind <= m) {
tr[ind] += x;
ind += lowbit(ind);
}
}
int getsum(int ind) {
int ret = 0;
while (ind) {
ret += tr[ind];
ind -= lowbit(ind);
}
return ret;
}
int main() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++) {
int a;
scanf("%d", &a);
q[a] = i;
}
for (int i = 1; i <= m; i++) {
scanf("%d", &h[i]);
srt[i] = h[i];
}
sort(srt + 1, srt + m + 1);
int len = unique(srt + 1, srt + m + 1) - srt - 1;
for (int i = 1; i <= m; i++) {
h[i] = lower_bound(srt + 1, srt + len + 1, h[i]) - srt;
}
cnt[n + 1] = -0x7fffffff;
for (int i = 1; i <= n; i++) {
cnt[i] = getsum(q[i]);
updata(q[i], 1);
}
for (int i = 1; i <= m; i++) {
tr[i] = 0;
}
for (int i = 2, j = 0; i <= n; i++) {
while (j && getsum(q[i]) != cnt[j + 1]) {
for (int k = i - j; k < i - nxt[j]; k++) updata(q[k], -1);
j = nxt[j];
}
if (getsum(q[i]) == cnt[j + 1]) {
j++; updata(q[i], 1);
}
nxt[i] = j;
}
for (int i = 1; i <= m; i++) {
tr[i] = 0;
}
for (int i = 1, j = 0; i <= m; i++) {
while (j && getsum(h[i]) != cnt[j + 1]) {
for (int k = i - j; k < i - nxt[j]; k++) updata(h[k], -1);
j = nxt[j];
}
if (getsum(h[i]) == cnt[j + 1]) {
j++;
updata(h[i], 1);
}
if (j == n) {
ans[++sz] = i - n + 1;
}
}
printf("%d
", sz);
for (int i = 1; i <= sz; i++) {
printf("%d ", ans[i]);
}
puts("");
return 0;
}