Set(01字典树合并+延迟更新)

描述

传送门:ACM-ICPC 2018 南京赛区网络预赛 - Problem H

Shinku is very interested in the set. One day, she got $n$ sets, and the $i$-th number $a_i$​ is in the $i$-th set. But she doesn’t think it is interesting enough, so she applies mmm magic to these sets. There are three kinds of magic:

1 $1\ u\ v$: If the uuu-th and $v$-th numbers are not in one set, then the Shinku’s magic will merge the set containing the $u$-th number and the set containing the $v$-th number.

2 $2\ u$: Shinku’s magic adds $1$ to each number in the set containing the $u$-th number.

3 $3\ u\ k\ x$: Shinku can immediately know how many numbers $t$ in the set containing the $u$-th number satisfy $t\equiv x (\bmod\ 2^k)(0 \le k\le 30,0\le x<2^k)$.

But unfortunately, for some reason the type $3$ magic fails. So Shinku wants you to tell her the answer after every type $3$ magic.

Note that there can be multiple numbers with the same value in one set, that is, numbers with the same value will not disappear when merged.

Input

The first line contains two integers $n, m(1 \le n, m \le 6 \times 10^5)$, the number of initial sets and the number of the magic.

The second line contains nnn integers. The $i$-th number $a_i(0 \le a_i \le 10^9)$ is the number in the $i$-th set initially.

The next $m$ lines describe the sequence of magic. The $i$-th line describes the $i$-th magic. Each magic is a magic as described above.

Output

For each type $3$ magic, output the answer you are asked to calculate.

Hint

After the first operation, the numbers are $2,3,4$, sets are $\lbrace 2,4 \rbrace \lbrace 3 \rbrace$

For the second operation, the third number is in $\lbrace 2,4 \rbrace, 2 \equiv 0\pmod {2^1}, 4 \equiv 0\pmod {2^1}$, so the answer is $2$.

After the third operation, the numbers are $2,4,4$, sets are $\lbrace 2,4 \rbrace \lbrace 4 \rbrace$

After the forth operation, the numbers are $2,4,4$, sets are $\lbrace 2,4,4 \rbrace$

For the fifth operation, ,the third number is in $\lbrace 2,4,4 \rbrace, 2 \equiv 0\pmod {2^1}, 4 \equiv 0\pmod {2^1}$,
$4 \equiv 0\pmod {2^1}$, so the answer is $3$.

样例输入

1
2
3
4
5
6
7
3 5
2 3 4
1 1 3
3 3 1 0
2 2
1 2 3
3 3 1 0

样例输出

1
2
2
3

思路

  • 容易想到使用01字典树来维护一个size域。
  • 这样的话第三个操作就是查询字典树上某个结点size的值。
  • 第一个操作就是字典树的合并,类似线段树的合并,需要利用可持久化的思想共用结点来节约内存。
  • 第二个操作就是打懒标记。在下推的时候,如果懒标记是个奇数就意味着要交换左右子树。
  • 内存卡得比较紧,写了vector内存池就MLE了QAQ。
  • 具体实现见代码。(难得写一次指针感觉还是蛮舒服的)
  • 实际上pushdown只会递归交换一条链上的点的左右子树,因此不打懒标记也可以。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include <bits/stdc++.h>
using namespace std;

const int maxn = 2e7;
struct Node
{
int sz, tag;
Node* ch[2];
Node() : sz(0), tag(0) { memset(ch, 0, sizeof(ch)); }
void maintain()
{
sz = 0;
if (ch[0] != nullptr) sz += ch[0]->sz;
if (ch[1] != nullptr) sz += ch[1]->sz;
}
void pushdown()
{
if (tag == 0) return;
if (tag & 1)
{
swap(ch[0], ch[1]);
if (ch[0] != nullptr) ch[0]->tag++;
}
if (tag > 1)
{
if (ch[0] != nullptr) ch[0]->tag += (tag >> 1);
if (ch[1] != nullptr) ch[1]->tag += (tag >> 1);
}
tag = 0;
}
} mem[maxn];

Node* newNode()
{
static int tot = 0;
assert(tot + 1 < maxn);
return &mem[tot++];
};

struct Trie
{
void insert(Node*& o, int x, int dep = 30)
{
if (o == nullptr) o = newNode();
if (dep == 0)
{
o->sz++;
return;
}
o->pushdown();
insert(o->ch[x & 1], x >> 1, dep - 1);
o->maintain();
}
Node* merge(Node* o, Node* k, int dep = 30)
{
if (o == nullptr) return k;
if (k == nullptr) return o;
if (o == nullptr && k == nullptr) return nullptr;
if (dep == 0)
{
o->sz += k->sz;
return o;
}
o->pushdown(), k->pushdown();
o->ch[0] = merge(o->ch[0], k->ch[0], dep - 1);
o->ch[1] = merge(o->ch[1], k->ch[1], dep - 1);
o->maintain();
return o;
}
int query(Node* o, int x, int dep)
{
if (o == nullptr) return 0;
if (dep == 0) return o->sz;
o->pushdown();
return query(o->ch[x & 1], x >> 1, dep - 1);
}
};

struct DSU
{
vector<int> fa;
DSU() {}
DSU(int n) { fa.resize(n), iota(fa.begin(), fa.end(), 0); }
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
bool same(int x, int y) { return find(x) == find(y); }
void merge(int x, int y) { fa[find(y)] = find(x); }
};

int main()
{
int n, m;
scanf("%d%d", &n, &m);
DSU d(n);
Trie t;
vector<Node*> rt(n);
for (int i = 0, x; i < n; i++)
{
scanf("%d", &x);
t.insert(rt[i], x);
}
while (m--)
{
static int op, u, v, k, x;
scanf("%d", &op);
if (op == 1)
{
scanf("%d%d", &u, &v);
--u, --v;
if (!d.same(u, v))
{
rt[d.find(u)] = t.merge(rt[d.find(u)], rt[d.find(v)]);
d.merge(u, v);
}
}
else if (op == 2)
{
scanf("%d", &u);
--u;
rt[d.find(u)]->tag++;
}
else
{
scanf("%d%d%d", &u, &k, &x);
--u;
printf("%d\n", t.query(rt[d.find(u)], x, k));
}
}
return 0;
}
捐助作者
0%