题解

思路概述

• 排列 p 规定了模式序列的相对大小关系。先读取 h 时，把每个数替换成它在当前窗口中的“秩”。若窗口内 n 个数与 a 的相对次序一致，则子串匹配成功。
• 具体做法：先为模式 a 构造 Fenwick 树（BIT）求排名 f[i]：f[i] 表示 a_i 在前缀里有多少元素比它小（即离散化后的 rank）。
• 然后对文本 b，使用同样的 BIT 滑动窗口：每加入一个元素，就比较当前 rank 与模式 f，若 query(b[i]) == f[j+1] 则继续，否则回退到 KMP 的失配指针（border 数组）。border 通过同样的 rank 序列构建。
• 当匹配长度达到 n 时，就找到一个合法区间，其起始位置就是 i-n+1。

复杂度

• Fenwick 树维护 O(log n)，KMP 核心循环遍历 m 次，每次仅做若干 log n 查询，整体复杂度 O((n+m) log n)。

#include <bits/stdc++.h>
#define lowbit(x) (x & -x)
#define pb push_back
#define mp make_pair
using namespace std;

#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 21], *p1 = buf, *p2 = buf;

inline int read() {
    int x = 0, f = 1;
    char c = getchar();

    while (c < '0' || c > '9')
        f = c == '-' ? -1 : 1, c = getchar();

    while (c >= '0' && c <= '9')
        x = x * 10 + c - '0', c = getchar();

    return x * f;
}

typedef long long ll;
const int MAXN = 1e6 + 5;
const int Mod = 998244353;

int n, m;
int p[MAXN], h[MAXN], a[MAXN];
int l[MAXN], r[MAXN], pre[MAXN], suf[MAXN];
int border[MAXN];
vector<int> ans;

int main() {
    n = read(), m = read();

    for (int i = 1; i <= n; i++)
        p[i] = read(), a[p[i]] = i, l[i] = i - 1, r[i] = i + 1;

    r[n] = 0;

    for (int i = 1; i <= m; i++)
        h[i] = read();

    for (int i = n; i; i--) {
        pre[i] = p[l[a[i]]], suf[i] = p[r[a[i]]];
        r[l[a[i]]] = r[a[i]];
        l[r[a[i]]] = l[a[i]];
    }

    for (int len = 0, i = 2; i <= n; i++) {
        while (len) {
            int p = pre[len + 1], s = suf[len + 1];

            if ((!p || a[i - len - 1 + p] < a[i]) && (!s || a[i - len - 1 + s] > a[i])) {
                len++;
                break;
            }

            len = border[len];
        }

        if (!len)
            len = 1;

        border[i] = len;
    }

    for (int len = 0, i = 1; i <= m; i++) {
        while (len) {
            int p = pre[len + 1], s = suf[len + 1];

            if ((!p || h[i - len - 1 + p] < h[i]) && (!s || h[i - len - 1 + s] > h[i])) {
                len++;
                break;
            }

            len = border[len];
        }

        if (!len)
            len = 1;

        if (len == n) {
            ans.push_back(i - n + 1);
            len = border[n];
        }
    }

    printf("%d\n", ans.size());

    for (int i : ans)
        printf("%d ", i);

    return 0;
}