专栏文章

P5607 [Ynoi2013] 无力回天 NOI2017 题解

AArgvchs
P5607题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mip5dg5a
此快照首次捕获于
2025/12/03 06:26
3 个月前
此快照最后确认于
2025/12/03 06:26
3 个月前
查看原文
首先你把并集转交集。
然后你考虑对值的出现次数根号分治。
出现次数 >B> B 的 bitset 维护，修改 O(1)O(1)，查询 O(m/Bw)O(\sqrt{m/Bw})。
但是出现次数 ≤B\le B 的呢？你哈希表维护集合两两之间答案就行了，修改 O(B)O(B)，查询 O(1)O(1)。
这里取 B=m/wB = \sqrt{m/w} 理论最优，复杂度 O(mm/w)O(m\sqrt{m/w})。
这样就做完了。
但是写完你发现你死得很惨。
怎么办？你想不到神秘链表做法，考虑卡常。
你注意到 bitset 很快，于是将 bitset 开到很大。
但是还不够快。
你注意到哈希表很慢，要插入 O(mB)O(mB) 次，怎么办呢？
你发现查询只有 O(m)O(m) 次！
我们开局把所有询问放到哈希表里面，然后修改时判一下要不要改，这样就只有 O(m)O(m) 次插入了！
最后你发现空间爆炸了？
我们直接把哈希表和 bitset 都搞成指针，然后第一次插入的时候再分配内存，这样做就是对的！！！
代码很好写而且没有细节。
https://www.luogu.com.cn/record/219340349
CPP
#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';
            }
        }
    }
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...