C. Sofia and the Lost Operations

是否存在一个序列 $c_{1}, c_{2}, \dots, c_{m}$ ，使得按顺序执行修改操作 $(c_{i}, d_{i})$ (操作 $(c, d) \leftrightarrow a_{c} = d$ ) 后，原始数组 $a_{1}, a_{2}, \dots, a_{n}$ 能够变成数组 $b_{1}, b_{2}, \dots, b_{n}$ ？

Solution

双指针/二分/Hash

只要满足两个条件就可以判定存在：

$d_{m}$ 是 $b$ 数组中的一个元素(不然最后一个元素无法覆盖使得 $a$ 数组总至少有一个元素会与 $b$ 数组不一样)
设 $n e q$ 数组为 $a, b$ 数组不同元素的集合，则这个数组必须包含在 $d$ 数组中

双指针：（180ms）

$O (n \log n)$

void solve() {
    int n;cin >> n;
    vector<int> a(n + 1), b(n + 1);
    for (int i = 1;i <= n;i++)cin >> a[i];
    for (int i = 1;i <= n;i++)cin >> b[i];

    vector<int> neq;
    for (int i = 1;i <= n;i++) {
        if (a[i] != b[i]) neq.push_back(b[i]);
    }

    int m;cin >> m;
    vector<int> d(m);
    for (int i = 0;i < m;i++) cin >> d[i];

    if (!count(b.begin() + 1, b.end(), d[m - 1])) {
        cout << "NO\n";return;
    }
    sort(neq.begin(), neq.end());
    sort(d.begin(), d.end());

    int j = 0, i = 0;
    for (;i < neq.size() && j < m;) {
        if (neq[i] != d[j])j++;
        else i++, j++;
    }
    if (i < neq.size()) {
        cout << "NO\n";return;
    }
    cout << "YES\n";
}

二分：

超时了。用 erase 时间复杂度是 $O (n)$ 的，所以不可行。可以换一种二分写法，这里懒得写了。

void solve() {
    int n;cin >> n;
    vector<int> a(n + 1), b(n + 1);
    for (int i = 1;i <= n;i++)cin >> a[i];
    for (int i = 1;i <= n;i++)cin >> b[i];

    vector<int> neq;
    for (int i = 1;i <= n;i++) {
        if (a[i] != b[i]) neq.push_back(b[i]);
    }

    int m;cin >> m;
    vector<int> d(m);
    for (int i = 0;i < m;i++) cin >> d[i];

    if (!count(b.begin() + 1, b.end(), d[m - 1])) {
        cout << "NO\n";return;
    }
    sort(neq.begin(), neq.end());
    sort(d.begin(), d.end());

    for (int i = 0;i < neq.size();i++) {
        auto it = lower_bound(d.begin(), d.end(), neq[i]);
        if (it == d.end() || *it != neq[i]) {
            cout << "NO\n";return;
        }
        d.erase(it);
    }
    cout << "YES\n";
}

Hash（480ms）

$O (n \log n)$

void solve() {
    int n;cin >> n;
    vector<int> a(n + 1), b(n + 1);
    for (int i = 1;i <= n;i++)cin >> a[i];
    for (int i = 1;i <= n;i++)cin >> b[i];

    vector<int> neq;
    map<int, int>mp;
    for (int i = 1;i <= n;i++) {
        if (a[i] != b[i]) neq.push_back(b[i]), mp[b[i]]++;
    }

    int m;cin >> m;
    vector<int> d(m);
    map<int, int>mpd;
    for (int i = 0;i < m;i++) cin >> d[i], mpd[d[i]]++;

    if (!count(b.begin() + 1, b.end(), d[m - 1])) {
        cout << "NO\n";return;
    }

    for (auto [x, y] : mp) {
        if (!mpd.count(x)) {
            cout << "NO\n";return;
        } else {
            if (mpd[x] < y) {
                cout << "NO\n";return;
            }
        }
    }
    cout << "YES\n";
}

Solution

双指针 ：（180ms）

二分 ：

Hash（480ms）

双指针：（180ms）

二分：