P5607 [Ynoi2013] 无力回天 NOI2017 题解

一道很好的题，如果做法不当（像我）可能需要一些卡常。
Part 1. bitset 20tps

插入？并集？ \(1e5\) ？显然可以用 \(bitset\) 维护：

• 每次修改把第 \(x\) 个 \(bitset\) 中的第 \(y\) 位修改成1
  
• 每次查询将 \(x1\) 和 \(x2\) 两个 \(bitset\) 取或求1的个数即可
  

这样可以轻松获得20tps。
Code

[code]const int N = 1e5 + 5;int m;bitset b[N];void solve(){        cin >> m;        while(m--){                ll opt, x, y; cin >> opt >> x >> y;                if(opt == 1){                        b[x][y] = 1;                }else{                        cout  m;    for(int i = 1; i > opt >> x >> y;        if(opt == 1){                ++siz[x];                int x0, x1;            for(int num : vc[y]){                    x0 = x, x1 = num;                                if(x0 > x1) swap(x0, x1);                                ++ans[x0][x1];                        }            vc[y].pb(x);        }        else{            if(x == y){                    cout  q.opt >> q.x >> q.y;        if(q.opt == 1) ++cnt[q.y];        else if(q.x > q.y) swap(q.x, q.y);    }    for(int i = 1; i  B1) f = ++tot; maxn = tot;    for(int i = 1; i