【题目描述】
对于整数序列$(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}$的子串个数。
    第二行$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

    代码

    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
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    #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\n", sz);
    for (int i = 1; i <= sz; i++) {
    printf("%d ", ans[i]);
    }
    puts("");
    return 0;
    }

评论