题目描述
给定 \(n\)个数 $a_i$, 起初第 \(i\)个数在第 \(i\)个集合. 有三种操作 (共 \(m\) 次):
1 $u$ $v$ 将第 $u$ 个数和第 $v$ 个数所在集合合并
2 $u$ 将第 $u$ 个数所在集合所有数加 1
3 $u$ $k$ $x$ 问 $u$ 所在集合有多少个数模 $2^k$ 余 $x$.
数据范围:\(n,m \le 500000,a_i \le 10^9, 0 \le k \le 30\).
简要题解
首先用并查集维护连通性.
下面先考虑操作 3, 这相当于询问低 $k$ 位二进制固定时集合中元素个数, 可以用 Trie 树, 维护一个子树中终结结点有多少个即可.
对于加 1 操作, 可以在 Trie 树上打标记, 类似线段树进行 pushDown 标记下传.
对于合并操作, 类似线段树合并. 由于初始时 \(n\)个数共需要 \(n \log 10^9\)个结点, 共 Trie 树合并的时间复杂度也为 \(n \log 10^9\). 关于线段树合并, 可以做这道入门题练手: Codeforces Gym 101194G http://codeforces.com/gym/101194/attachments (2016EC Final)
总时间复杂度 \((n+q) \log 10^9\).
注意事项
此题空间复杂度 \(n \log 10^9\). 如果 Trie 树合并使用新开的结点, 每个结构体 16B, 将需要 576MB, 这会 MLE. 考虑 Trie 树合并时不新开结点, 可以将空间降至 288MB.
完整代码
- #include<cstdio>
- #include<cstring>
- #include<vector>
- #define DEPTH 30
- using namespace std;
- struct Trie{
- int size;
- int next[2];
- int tag;
- }trie[20000001];
- int cnt;
- int newTrie(){
- memset(&trie[++cnt], 0, sizeof(Trie));
- return cnt;
- }
- inline void pushDown(int i){
- int &t = trie[i].tag;
- int &l = trie[i].next[0], &r = trie[i].next[1];
- if (t){
- if (t & 1){ swap(l, r); trie[l].tag++; }
- if (t>= 2){ trie[l].tag += t / 2; trie[r].tag += t / 2; }
- t = 0;
- }
- }
- inline void pushUp(int i){
- trie[i].size = trie[trie[i].next[0]].size + trie[trie[i].next[1]].size;
- }
- void insert(int i, int depth, int x)
- {
- if (!depth){ trie[i].size++; return; }
- pushDown(i);
- int &pos = trie[i].next[x & 1];
- if (!pos)pos = newTrie();
- insert(pos, depth - 1, x>> 1);
- pushUp(i);
- }
- void merge(int& i, int j, int k, int depth)
- {
- if (j&&k){
- i = j;
- if (!depth){
- trie[i].size += trie[k].size;
- return;
- }
- pushDown(j); pushDown(k);
- for (int c = 0; c <2; c++)
- merge(trie[i].next[c], trie[j].next[c], trie[k].next[c], depth - 1);
- pushUp(i);
- }
- else i = j ? j : k;
- }
- int f[600001], id[600001];
- int getFather(int i)
- {
- if (f[i] == i)return i;
- return f[i] = getFather(f[i]);
- }
- int main()
- {
- int n, m, x, u, v, k;
- scanf("%d%d", &n, &m);
- for (int i = 1; i <= n; i++){
- scanf("%d", &x);
- id[i] = newTrie();
- f[i] = i;
- insert(id[i], DEPTH, x);
- }
- while (m--){
- scanf("%d%d", &x, &u);
- u = getFather(u);
- if (x == 1){
- scanf("%d", &v);
- v = getFather(v);
- if (u != v){
- f[u] = v;
- merge(id[v], id[u], id[v], DEPTH);
- }
- }
- else if (x == 2)trie[id[u]].tag++;
- else{
- scanf("%d%d", &k, &x);
- int cur;
- for (cur = id[u]; k; k--){
- pushDown(cur);
- cur = trie[cur].next[x & 1];
- if (!cur)break;
- x>>= 1;
- }
- if (!cur)printf("0\n");
- else printf("%d\n", trie[cur].size);
- }
- }
- }
来源: https://www.cnblogs.com/zbh2047/p/9572187.html