【ACM-ICPC 2018 南京赛区网络预赛】Set <并查集+Trie合并>

Problem

【ACM-ICPC 2018 南京赛区网络预赛】Set

$\mathrm{Time\;Limit:\;1500\;ms}$
$\mathrm{Memory\;Limit:\;524288\;K}$

Description

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 $m$ magic to these sets. There are three kinds of magic:

• $1\;u\;v$: If the $u^{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\;u$: Shinku’s magic adds $1$ to each number in the set containing the $u^{th}$ number.
• $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 $n$ 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.

Sample Input

3 5
2 3 4
1 1 3
3 3 1 0
2 2
1 2 3
3 3 1 0

Sample Output

2
3

Explanation

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$.

Source

ACM-ICPC 2018 南京赛区网络预赛

标签：并查集 Trie合并

Translation

给定一个长为$n$ $(n\le5\cdot10^5)$的序列$\lbrace a\rbrace$ $(a_i\le10^9)$，起初第$i$个数在第$i$个集合。
有$m$ $(m\le5\cdot10^5)$个操作，分为三类：

• $1\;u\;v$ 将第$u$个数和第$v$个数所在集合合并
• $2\;u$ 将第$u$个数所在集合所有数加$1$
• $3\;u\;k\;x$ 问$u$所在集合有多少个数模$2^k$余$x$ $(k\le 30)$

对于每个$3$询问，输出答案。

Solution

探索题目条件的特殊性，发现所有询问均是对$2^k$取模。
我们将每个数转为二进制后倒置，则询问变为含有$x$转为二进制倒置作为前缀的二进制串的个数，可以用$\mathrm{Trie}$维护。那么$1$操作相当于合并两个$\mathrm{Trie}$，可以用类似线段树合并的做法完成，需要用并查集维护连通性。
对于$2$操作，由于每个数都倒置了，可以模拟从最后一位向前进位。于是给结点打上标记，每次下传时将标记除$2$传到下一层，特别地，如果当前层标记是奇数，则需要交换两个子树，因为进位会使$0$变为$1$，$1$变为$0$。
总时间复杂度$O((n+q)\log10^9)$。
$\mathrm{P.S.}$貌似对$2$操作可以暴力向下递归交换子树。

Code

#include <bits/stdc++.h>
#define MAX_N 600000
using namespace std;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m, sz, rt[MAX_N+5], fa[MAX_N+5];
struct node {int s[2], c, tag;} tr[MAX_N*32];
int getf(int x) {return fa[x] == x ? x : fa[x] = getf(fa[x]);}
void downtag(int v) {
    if (!tr[v].tag) return;
    if (tr[v].tag&1)
        tr[tr[v].s[1]].tag++, 
        swap(tr[v].s[0], tr[v].s[1]);
    if (tr[v].tag > 1)
        tr[tr[v].s[0]].tag += (tr[v].tag>>1), 
        tr[tr[v].s[1]].tag += (tr[v].tag>>1);
    tr[v].tag = 0;
}
void insert(int &v, int dep, int x) {
    if (!v) v = ++sz;
    if (!dep) {tr[v].c++; return;}
    insert(tr[v].s[x&1], dep-1, x>>1);
    tr[v].c = tr[tr[v].s[0]].c+tr[tr[v].s[1]].c;
}
int merge(int u, int v) {
    if (!u) return v; if (!v) return u;
    downtag(u), downtag(v);
    tr[u].s[0] = merge(tr[u].s[0], tr[v].s[0]);
    tr[u].s[1] = merge(tr[u].s[1], tr[v].s[1]);
    tr[u].c += tr[v].c; return u;
}
int main() {
    read(n), read(m);
    for (int i = 1, x; i <= n; i++)
        fa[i] = i, read(x), insert(rt[i], 30, x);
    while (m--) {
        int opt, p, u, v, k, x; read(opt);
        if (opt == 1) {
            read(u), read(v), u = getf(u), v = getf(v);
            if (u^v) fa[v] = u, rt[u] = merge(rt[u], rt[v]);
        }
        if (opt == 2) read(p), tr[rt[getf(p)]].tag++;
        if (opt == 3) {
            read(p), read(k), read(x), p = rt[getf(p)];
            for (; k; k--, p = tr[p].s[x&1], x >>= 1) downtag(p);
            printf("%d\n", p ? tr[p].c : 0);
        }
    }
    return 0;
}