原题

给定长度为 n 的序列 a_1,a_2,...,a_n，以及长度为 m 的序列 b_1,b_2,...,b_m。判断 a 中是否存在两个都等于 b 的子序列，并且这两个子序列使用的下标没有交集。存在则输出 Yes，否则输出 No。

子序列指删除原序列若干元素后，保留其余元素原有相对顺序得到的序列。题目保证 b 中的数字互不相同。

输入第一行是两个整数 n,m (2<=n<=3×10^5, 1<=m<=floor(n/2))；第二行是 n 个整数 a_i (1<=a_i<=10^9)；第三行是 m 个整数 b_i (1<=b_i<=10^9)。

输出 Yes 或 No。

样例 1：

输入
6 3
1 1 2 2 3 3
1 2 3

输出
Yes

样例 2：

输入
6 3
2 2 1 1 3 3
1 2 3

输出
No

题解

MC0478 夜袭粮仓（C++17）

判断序列 a 中能否选出两组下标互不重合的子序列，并且两组都按顺序等于 b。b 中的数两两不同，这是线性扫描能成立的关键。

把 b_k 记为目标序列的第 k 个数。因为 b 里没有重复值，a 中一个等于 b_k 的元素，只可能去匹配第 k 位，不会有“到底匹配哪一位”的歧义。没出现在 b 中的值直接跳过。

从左到右扫描 a，维护 p、q：两条子序列已经分别匹配了 b 的多少个元素。读到一个值 x 后：

• 若 x=b_p，把它分配给第一条子序列，令 p++；
• 否则若 x=b_q，把它分配给第二条子序列，令 q++；
• 其他情况跳过。

一个位置一旦被分给某条序列，就不会再次使用，所以两条子序列不会重叠。每条序列的进度只能按 0,1,...,m-1 前进，顺序也不会乱。

贪心的关键在于“优先给第一条”其实没有损失。若 p 和 q 不同，当前 x 至多匹配一条，根本没有选择；若二者相同，两条序列可以互换名字，给谁都一样。能推进就立刻使用，只会让其中一条更早走到后面，不会妨碍另一条使用之后的元素。

状态就是 (p,q)。初始为 (0,0)，表示尚未选任何元素；扫描每个 a_i 只可能推进其中一个分量。两个分量都达到 m 时，已经得到两条完整且下标不重合的 b，输出 Yes。若扫描结束仍未达到，则输出 No。m>=1，而 m<=floor(n/2) 只是保证长度上存在可能，并不保证一定可行。

用哈希表记录每个 b_k 的下标。时间复杂度为期望 O(n+m)，空间复杂度为 O(m)，满足 n<=3×10^5。

代码

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<int> a(n);
    for (int &value : a) {
        cin >> value;
    }

    unordered_map<int, int> pos;
    pos.reserve(2 * m);
    for (int i = 0; i < m; ++i) {
        int x;
        cin >> x;
        pos[x] = i;
    }

    int p = 0;
    int q = 0;

    for (int x : a) {
        auto it = pos.find(x);
        if (it == pos.end()) {
            continue;
        }

        int k = it->second;
        if (p < m && k == p) {
            ++p;
        } else if (q < m && k == q) {
            ++q;
        }
    }

    cout << (p == m && q == m ? "Yes" : "No") << '\n';
    return 0;
}

实现核对

pos[x] 是满足 b_k=x 的唯一位置 k；p、q 是两条子序列已经匹配的长度；二者都等于 m 时对应存在两条合法子序列。