题解：P10785 [NOI2024] 集合

Usada_Pekora · 2024-07-25 23:46:05 · 题解

当值 i 在 A_{[l,r]} 中出现的下标集合与值 j 在 B_{[l,r]} 中出现的下标集合相同时，置换 f_i=j 便是合法的。那么，当所有在 A_{[l,r]} 中出现的值 i 都可以在 B_{[l,r]} 中不重复地找到这样一个 j，答案就是 Yes。

想办法维护下标集合的出现次数，对下标集合 hash 一下就好做了，给每个位置赋一个 2^{64} 范围的随机值，规定下标集合的 hash 值是里面所有位置的赋值的 xor，冲突的概率是 2^{-64}，可以假设两个不同集合的 hash 值不同。

到这里可以莫队，用 unordered_map 维护，A 里面的下标集合的权是 1，B 里面的是 -1，那么所有 hash 值的权和都是 0 就是 Yes。

但 O(n\sqrt q) 跑过去很难，显然，对于所有 l，答案是 Yes 存在分界点 p_l，且 p_l 是随着 l 单调不减的，双指针就好了。

#include <bits/stdc++.h>
#define pb emplace_back
#define mkp make_pair
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
template<typename T> inline bool chkmin(T &x, const T &y) {
    return (y < x) && (x = y, true);
}
template<typename T> inline bool chkmax(T &x, const T &y) {
    return (x < y) && (x = y, true);
}
constexpr int N = 1e6 + 5;
int n, m, q, a[N][3], b[N][3], p[N], tot;
ull A[N], B[N], rd[N];
mt19937 rng(1u * time(NULL));
inline void ins(ull x, int opt) {
    static unordered_map<ull, int> cnt;
    if (cnt[x] != 0)
        tot--;
    if ((cnt[x] += opt) != 0)
        tot++;
}
inline void work(int i) {
    for (int j = 0; j < 3; j++) {
        ins(A[a[i][j]], -1), A[a[i][j]] ^= rd[i], ins(A[a[i][j]], 1);
        ins(B[b[i][j]], 1), B[b[i][j]] ^= rd[i], ins(B[b[i][j]], -1);
    }
}
signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> m >> q;
    for (int i = 1; i <= n; i++)
        for (int j = 0; j < 3; j++)
            cin >> a[i][j];
    for (int i = 1; i <= n; i++)
        for (int j = 0; j < 3; j++)
            cin >> b[i][j];
    for (int i = 1; i <= n; i++)
        rd[i] = rng();
    for (int l = 1, r = 0; l <= n; l++) {
        while (r <= n && tot == 0)
            work(++r);
        p[l] = r;
        work(l);
    }
    while (q--) {
        int l, r;
        cin >> l >> r;
        cout << ((p[l] > r) ? "Yes\n" : "No\n");
    }
    return 0;
}