P5607 [Ynoi2013] 无力回天 NOI2017 题解

· · 题解

首先你把并集转交集。

然后你考虑对值的出现次数根号分治。

出现次数 > B 的 bitset 维护，修改 O(1)，查询 O(\sqrt{m/Bw})。

但是出现次数 \le B 的呢？你哈希表维护集合两两之间答案就行了，修改 O(B)，查询 O(1)。

这里取 B = \sqrt{m/w} 理论最优，复杂度 O(m\sqrt{m/w})。

这样就做完了。

但是写完你发现你死得很惨。

怎么办？你想不到神秘链表做法，考虑卡常。

你注意到 bitset 很快，于是将 bitset 开到很大。

但是还不够快。

你注意到哈希表很慢，要插入 O(mB) 次，怎么办呢？

你发现查询只有 O(m) 次！

我们开局把所有询问放到哈希表里面，然后修改时判一下要不要改，这样就只有 O(m) 次插入了！

最后你发现空间爆炸了？

我们直接把哈希表和 bitset 都搞成指针，然后第一次插入的时候再分配内存，这样做就是对的！！！

代码很好写而且没有细节。

https://www.luogu.com.cn/record/219340349

#include <bitset>
#include <ext/pb_ds/assoc_container.hpp>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;
const int N = 1e6 + 5, B1 = 8192, B2 = N / B1;
int m, op[N], x[N], y[N], cnt[N], siz[N], id[N], lim, idx;
bitset<B1> *b[N];
vector<int> v[N];
__gnu_pbds::gp_hash_table<int, int> *f[N];
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> m;
    for (int i = 1; i <= m; i++) {
        cin >> op[i] >> x[i] >> y[i];
        if (op[i] == 1) ++cnt[y[i]];
        else if (x[i] > y[i]) swap(x[i], y[i]);
    }
    for (int i = 1; i <= m; i++)
        if (cnt[i] > B2) id[i] = ++idx;
    lim = idx;
    for (int i = 1; i <= m; i++)
        if (cnt[i] <= B2) id[i] = ++idx;
    for (int i = 1; i <= m; i++)
        if (op[i] == 1) y[i] = id[y[i]];
    for (int i = 1; i <= m; i++)
        if (op[i] == 2) {
            if (!f[x[i]]) f[x[i]] = new __gnu_pbds::gp_hash_table<int, int>();
            (*f[x[i]])[y[i]] = 0;
        }
    for (int i = 1; i <= m; i++) {
        if (op[i] == 1) {
            ++siz[x[i]];
            if (y[i] <= lim) {
                if (!b[x[i]]) b[x[i]] = new bitset<B1>();
                b[x[i]]->set(y[i]);
            } else {
                for (int j : v[y[i]]) {
                    int x0 = x[i], y0 = j;
                    if (x0 > y0) swap(x0, y0);
                    if (f[x0] && f[x0]->find(y0) != f[x0]->end()) ++(*f[x0])[y0];
                }
                v[y[i]].push_back(x[i]);
            }
        } else {
            if (x[i] == y[i]) cout << siz[x[i]] << '\n';
            else {
                int t = (*f[x[i]])[y[i]];
                if (b[x[i]] && b[y[i]]) t += (*b[x[i]] & *b[y[i]]).count();
                cout << siz[x[i]] + siz[y[i]] - t << '\n';
            }
        }
    }
}