P5607 [Ynoi2013] 无力回天 NOI2017 题解

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

Part 1. bitset 20tps

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

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

这样可以轻松获得20tps。

Code

const int N = 1e5 + 5;int m;
bitset<N> 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 << (b[x] | b[y]).count() << "\n";}}
}

Part 2. 哈希表 34tps

考虑其实只需要维护两两之间的答案，最多 \(m\) 组

• 每次修改把所有修改过 \(y\) 的和当前的集合间的交集大小加1，并记录每个集合的大小
• 每次查询将两个集合相加减去并集即可

这样可以轻松获得34tps。（注：pb_ds哈希表使用方法在最后）

Code

const int N = 1e6 + 5;int m, maxn, siz[N];
cc_hash_table<int, int> ans[N];
vector<int> vc[N];void solve(){cin >> m;for(int i = 1; i <= m; i++){int opt, x, y; cin >> 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 << siz[x] << "\n";continue;}if(x > y) swap(x, y);int ans1 = ans[x][y];cout << siz[x] + siz[y] - ans1<< "\n";}}
}

Part 3. 正解 100tps

我们思考，

• \(bitset\) 的优势在于高效处理多次出现，缺点是空间开不下
• 哈希表的优势在于空间小，缺点是多次出现时会TLE

怎么办呢？考虑结合以上两种做法，对于多次出现交给 \(bitset\) 处理，其他数据由空间小的哈希表处理。

具体的，考虑进行根号分治，设临界值为 \(B\) ，记 \(x\) 的出现次数为 \(cnt_x\) ，对于每个数 \(x\)：

• 若 \(cnt_x<B\) ，用哈希表处理
• 若 \(cnt_x>B\) ，用 \(bitset\) 处理

考虑到 \(bitset\) 的复杂度，当 \(B=\sqrt{m/w}\)时达到理论最优值

直接写完你就会发现MLE，怎么办？只需要改成出生可可爱爱の指针就可以了！

Code

const int N = 1e6 + 5, B = 8192, B1 = N / B;int m, maxn, siz[N];
struct node{int opt, x, y;
} q[N];
bitset<B> *b[N];
cc_hash_table<int, int> *ans[N];
vector<int> vc[N];
int cnt[N], f[N], tot;void init(){cin >> m;for(int i = 1; i <= m; i++){cin >> q[i].opt >> q[i].x >> q[i].y;if(q[i].opt == 1) ++cnt[q[i].y];else if(q[i].x > q[i].y) swap(q[i].x, q[i].y);}for(int i = 1; i <= m; i++) if(cnt[i] > B1) f[i] = ++tot; maxn = tot;for(int i = 1; i <= m; i++) if(cnt[i] <= B1) f[i] = ++tot;for(int i = 1; i <= m; i++) if(q[i].opt == 1) q[i].y = f[q[i].y];for(int i = 1; i <= m; i++) if(q[i].opt == 2){if(!ans[q[i].x]) ans[q[i].x] = new cc_hash_table<int, int>();(*ans[q[i].x])[q[i].y] = 0;}
}
void solve(){for(int i = 1; i <= m; i++){if(q[i].opt == 1){++siz[q[i].x];if(q[i].y <= maxn){if(!b[q[i].x]) b[q[i].x] = new bitset<B>();(*b[q[i].x])[q[i].y] = 1;}else{int x0, x1;if(vc[q[i].y].size() != 0){for(int num : vc[q[i].y]){x0 = q[i].x, x1 = num;if(x0 > x1) swap(x0, x1);if(!ans[x0]) continue;if(ans[x0] -> find(x1) != ans[x0] -> end()) ++(*ans[x0])[x1];}}vc[q[i].y].pb(q[i].x);}}else{if(q[i].x == q[i].y){cout << siz[q[i].x] << "\n";continue;}int ans1 = (*ans[q[i].x])[q[i].y], ans2 = 0;if(b[q[i].x] && b[q[i].y]) ans2 = (*b[q[i].x] & *b[q[i].y]).count();cout << siz[q[i].x] + siz[q[i].y] - ans1 - ans2 << "\n";}}
}

Part 4. 补充

pb_ds使用须知：

请使用以下头文件

#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/priority_queue.hpp>
#include<ext/pb_ds/exception.hpp>
#include<ext/pb_ds/hash_policy.hpp>
#include<ext/pb_ds/list_update_policy.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/trie_policy.hpp>
using namespace __gnu_pbds;