可持久化线段树（主席树）lyh's blog

        正式开始可持久化数据结构。

        数据结构可以维护很多信息，但是可持久化数据结构又是什么？考虑这样一个问题：现在维护一个数组，需要修改或者访问其中的某一个元素，如何维护？~~这问题太智障了~~，如果需要访问或修改某一个历史版本又如何操作？查询和修改历史版本普通的数据结构是做不到的，这时就可以祭出可持久化数据结构。可持久化数据结构可以维护历史版本信息。
        可持久化线段树是一类重要的可持久化数据结构，又称主席树。主席树的优点是支持可持久化，时间复杂度比较好，缺点是空间占用大。

静态区间第k小问题

        引入主席树之前，先来了解一下一个经典问题：静态区间第k小。即给定一个序列，查询某一个区间中第k小的数。
        如果每一次查询都排一次序，这样效率极低无比。这个问题可以用主席树轻松地解决，也是引入主席树的经典问题。当然本题用树套树、分块应该也能卡过去。
        模板题：戳这里。
        首先，需要将原有数据离散化。离散化方法是将序列数据排序，去重。比如对于3、5、8、3、1序列，去重后得到1、3、5、8，这样这些数就可以重新标号，起到离散化效果。
        这一步的代码如下：

1	sort(tmp + 1, tmp + n + 1), m = unique(tmp + 1, tmp + n + 1) - tmp - 1;//tmp是原数组的拷贝

        unique函数可以将有序数列进行去重，返回不重复序列的末尾元素的下一个元素位置。m记录互不相同的元素数目。
        这里的主席树其实是一棵权值线段树，即它的每一个结点记录的是某个数在区间中出现的次数。建一棵线段树，其储存区间[1,m]的信息，并表示对于原数组[1,n]，[i,j]中的数出现的次数，这里[i,j]是[1,m]的一个子集。比如说树根位置储存[1,m]的出现次数，就上面的例子而言，它的值为5，这是因为原数组[1,5]（指3、5、8、3、1）中[1,4]（指1、3、5、8）出现的次数，当然是5。同样地，其左子树根结点（储存[1,3]的信息）值应该为4。
        这样建树的好处是什么？设想一下现在如果要求原数组[1,p]区间中第k小的数，可以这样做：找到左子树的权值s，如果s<k，说明左子树对应的数不是第k小，答案必然在右子树上，否则就在左子树上。建好这一棵线段树后，查找[1,p]的区间第k小的问题就解决了。
        但是如果起始结点不为1怎么办？很明显，如果我们对于任一个元素i，都建立一棵[1,i]对应的线段树，共建n棵，这样利用区间可减性（前缀和思想）就可以找到[i,j]的对应值了，同样可以求出第k小的数。
        建立n棵线段树一定会MLE，从这里开始就体现出了主席树的优化方案：重用结点。
        对比[1,i]和[1,i+1]这两棵线段树，可以发现后者只不过是在前者基础上修改了从根开始的一段路径上的结点而已，它们有大量的点是可以共用的。这样，只需要把新的结点建立出来，重复的结点直接复用上一次的结点即可。
        主席树由许多棵线段树组成，每一个线段树有着自己独立的树根。现在来探讨如何初始化一棵主席树。
        在这里，约定用root[i]数组记录不同线段树的树根标号，并用统一的内存池来管理结点的分配。op为原数组，tmp为经排序并去重后的数组，V记录结点权值。

int build(int l, int r) {//构造[l,r]区间的线段树，这里的区间是tmp上的
    int rt = cnt++;//cnt分配结点，新分配一个，V初始化为0，由于V是全局变量，就不用再写了
    if (l < r)L[rt] = build(l, (l + r) >> 1), R[rt] = build(((l + r) >> 1) + 1, r);//记录左儿子、右儿子，递归进行
    return rt;
}

root[0] = build(1, m);//main函数中使用，这是第0棵线段树

下面考虑如何建一棵新树并重用上一个版本的结点，先看构树函数。

int newTree(int l, int r, int pre, int s) {//在区间[l,r]，前一个树（要复用的）的树根pre，修改第s个叶子结点
    int rt = cnt++;//分配一个新的结点
    L[rt] = L[pre], R[rt] = R[pre], V[rt] = V[pre] + 1;//默认左右儿子全部复用，但V要自加（加上新来的那一个数）
    if (l < r) {//对于可以再划分的区间
        if (s > ((l + r) >> 1))R[rt] = newTree(((l + r) >> 1) + 1, r, R[pre], s);//建右子树
        else L[rt] = newTree(l, (l + r) >> 1, L[pre], s);//建左子树
    }
    return rt;
}

上面的算法是容易理解的，在主函数中需要这样使用：

1	for (int i = 1; i <= n; i++)root[i] = newTree(1, m, root[i - 1], lower_bound(tmp + 1, tmp + m + 1, op[i]) - tmp);

每次都重用上一棵线段树。lower_bound可以在升序序列中找到第一个不小于op[i]的数的位置，新树的树根存放到root中。
查找自然也很方便，直接二分即可：

int query(int l, int r, int k, int a = 1, int b = m) {
    if (a == b)return tmp[a];//找到这个数
    if (V[L[r]] - V[L[l]] < k)return query(R[l], R[r], k - V[L[r]] + V[L[l]], ((a + b) >> 1) + 1, b);//向右子树上找
    return query(L[l], L[r], k, a, (a + b) >> 1);//向左子树上找
}

全代码：

#include<bits/stdc++.h>

#define N 200005
using namespace std;

inline int read() {
    char e = getchar();
    int s = 0, p = 0;
    while (e < '-')e = getchar();
    if (e == '-')p = 1, e = getchar();
    while (e > '-')s = (s << 1) + (s << 3) + (e & 15), e = getchar();
    return p ? -s : s;
}

int n, q, m, L[N << 6], R[N << 6], V[N << 6], op[N], tmp[N], root[N], cnt = 1, a, b, c;

int build(int l, int r) {
    int rt = cnt++;
    if (l < r)L[rt] = build(l, (l + r) >> 1), R[rt] = build(((l + r) >> 1) + 1, r);
    return rt;
}

int newTree(int l, int r, int pre, int s) {
    int rt = cnt++;
    L[rt] = L[pre], R[rt] = R[pre], V[rt] = V[pre] + 1;
    if (l < r) {
        if (s > ((l + r) >> 1))R[rt] = newTree(((l + r) >> 1) + 1, r, R[pre], s);
        else L[rt] = newTree(l, (l + r) >> 1, L[pre], s);
    }
    return rt;
}

int query(int l, int r, int k, int a = 1, int b = m) {
    if (a == b)return tmp[a];
    if (V[L[r]] - V[L[l]] < k)return query(R[l], R[r], k - V[L[r]] + V[L[l]], ((a + b) >> 1) + 1, b);
    return query(L[l], L[r], k, a, (a + b) >> 1);
}

int main() {
    n = read(), q = read();
    for (int i = 1; i <= n; i++)tmp[i] = op[i] = read();
    sort(tmp + 1, tmp + n + 1), m = unique(tmp + 1, tmp + n + 1) - tmp - 1;
    root[0] = build(1, m);
    for (int i = 1; i <= n; i++)root[i] = newTree(1, m, root[i - 1], lower_bound(tmp + 1, tmp + m + 1, op[i]) - tmp);
    while (q--)a = read(), b = read(), c = read(), printf("%d\n", query(root[a - 1], root[b], c));
    return 0;
}

好像到现在没有看到可持久化的意思？其实仔细观察上面的过程，可以认为上面的每一棵线段树都是一个历史版本，它维护的是后面元素尚未加入时的信息。也就是说，静态区间第k小虽然没有直接体现可持久化，但它实际上已经体现出来可持久化的思想了。

单点修改的动态区间第k小

        给定一个序列，求某一个区间的第k小值可以用主席树做出来。但是如果需要单点修改呢？这时主席树就不容易做了。如果修改x位置的值，我们需要修改x~n的所有树，效率很低。
        看到单点修改和前缀和，自然想到树状数组，因此可以考虑搭配树状数组和主席树来解决这个问题。
        方法比较容易实现。对于树状数组的每一个位置，都有一棵独立的权值线段树（就是主席树），它维护的范围与树状数组的定义相同。在上文的静态区间第k小中，曾用复用结点的方式来减小内存占用，但是树状数组中每一个位置所对应的权值线段树，很不容易复用结点，因此只能暴力开点。开n个线段树确实会MLE，但是如果选择动态开点，则可以将空间复杂度降低。~~但即使这样占用内存还是很大。~~
        另一个问题。一开始我们离散化原有序列，通过它们的排名来构造主席树，动态修改后可能会加入一些新的值，怎么去维护？这里确实不易做到，但仍有解决方法：离线。离线处理所有修改后的值，将它们与原序列一起进行离散化，就可以优雅地建树了。
        模板题：戳这里。

#include<bits/stdc++.h>

#define N 100005
using namespace std;
int lc[N * 600], rc[N * 600], cnt, tot, value[N * 600], tmp[N << 1], n, m, op[N], root[N];
int xx[N], yy[N], totx, toty;
struct Query {
    bool isC;
    int i, j, k;
} q[N];

void update(int &rt, int l, int r, int k, int x) {
    if (rt == 0)rt = ++cnt;
    value[rt] += x;
    if (l == r)return;
    int mid = (l + r) >> 1;
    if (k <= mid)update(lc[rt], l, mid, k, x);
    else update(rc[rt], mid + 1, r, k, x);

}

inline void modify(int x, int y) {
    int k = static_cast<int>(lower_bound(tmp + 1, tmp + tot + 1, op[x]) - tmp);
    for (; x <= n; x += (x & -x))update(root[x], 1, tot, k, y);
}

int query(int k, int l, int r) {//查询
    if (l == r)return l;
    int sum = 0, mid = (l + r) >> 1;
    for (int i = 1; i <= totx; i++)sum -= value[lc[xx[i]]];
    for (int i = 1; i <= toty; i++)sum += value[lc[yy[i]]];
    if (sum >= k) {
        for (int i = 1; i <= totx; i++)xx[i] = lc[xx[i]];//一起转移
        for (int i = 1; i <= toty; i++)yy[i] = lc[yy[i]];
        return query(k, l, mid);
    } else {
        for (int i = 1; i <= totx; i++)xx[i] = rc[xx[i]];
        for (int i = 1; i <= toty; i++)yy[i] = rc[yy[i]];
        return query(k - sum, mid + 1, r);
    }
}

int main() {
    char e;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)scanf("%d", tmp + i), op[i] = tmp[i];
    tot = n;
    for (int i = 1; i <= m; i++) {
        scanf(" %c", &e);
        if (e == 'C')q[i].isC = true, scanf("%d%d", &q[i].i, &q[i].j), tmp[++tot] = q[i].j;
        else q[i].isC = false, scanf("%d%d%d", &q[i].i, &q[i].j, &q[i].k);
    }
    sort(tmp + 1, tmp + tot + 1);
    tot = static_cast<int>(unique(tmp + 1, tmp + tot + 1) - tmp - 1);
    for (int i = 1; i <= n; i++)modify(i, 1);
    for (int i = 1; i <= m; i++) {
        if (q[i].isC)modify(q[i].i, -1), op[q[i].i] = q[i].j, modify(q[i].i, 1);
        else {
            totx = toty = 0;
            for (int j = q[i].i - 1; j > 0; j -= (j & -j))xx[++totx] = root[j];//存所有的树
            for (int j = q[i].j; j > 0; j -= (j & -j))yy[++toty] = root[j];
            printf("%d\n", tmp[query(q[i].k, 1, tot)]);
        }
    }
    return 0;
}

静态树上路径第k小

        现在考虑树上的问题。
        首先考虑一个更简单的问题：求有根树某一子树上点权第k小。这个很容易，一遍DFS重标号就转化为区间第k小，还可以很方便地转移到单点修改的动态第k小。
        树上路径就比较麻烦了，但思路仍然是主席树的思路。首先无根树转有根树（通常选1号结点为根），然后在树上建立主席树。对于某一个结点的若干个子结点，让这些子结点重用父结点对应主席树上的结点，就可以大大压缩空间，空间复杂度仍然是$O(nlogn)$。
        主席树易建，现在主要问题是如何查询。考虑之前我们是如何求某一路径上某个数的出现次数的：先预处理树上前缀和，然后求lca之后作差得到结果。这里的主席树本身就是求前缀和的利器，我们只需要求一下lca，然后三棵主席树同时转移，就可以得到任意一个点权在这个路径上的出现次数，求第k小的方法也就显而易见了。唯一需要注意的就是lca本身的点权需要在转移时计入。
        来看一道模板题：SP10628 COT。很裸（~~这还不够裸吗~~）的静态树上路径第k小，代码如下：

#include <bits/stdc++.h>

#define N 100005
using namespace std;
struct Node {
    int l, r, v;
} node[N << 6];
struct Edge {
    int to, next;
} edge[N << 1];
int cnt = 1, head[N], v[N], n, m, gr[N][25], dep[N], root[N], tmp[N], sv, ans;

inline void add(int x, int y) {
    static int c = 1;
    edge[c].to = y, edge[c].next = head[x], head[x] = c++;
}

int newTree(int pre, int s, int l = 1, int r = sv) {
    int p = cnt++, mid = (l + r) >> 1;
    node[p] = node[pre], ++node[p].v;
    if (l == r)return p;
    if (s > mid)node[p].r = newTree(node[pre].r, s, mid + 1, r);
    else node[p].l = newTree(node[pre].l, s, l, mid);
    return p;
}

void DFS(int x, int fa) {
    root[x] = newTree(root[fa], lower_bound(tmp + 1, tmp + sv + 1, v[x]) - tmp);
    for (int i = head[x]; i; i = edge[i].next) {
        if (!dep[edge[i].to]) {
            dep[edge[i].to] = dep[x] + 1, gr[edge[i].to][0] = x;
            for (int j = 1; j <= 24; j++)gr[edge[i].to][j] = gr[gr[edge[i].to][j - 1]][j - 1];
            DFS(edge[i].to, x);
        }
    }
}

inline int LCA(int x, int y) {//倍增求lca
    if (dep[x] > dep[y])swap(x, y);
    for (int i = 24; i >= 0; i--)if (dep[gr[y][i]] >= dep[x])y = gr[y][i];
    if (x == y)return x;
    for (int i = 24; i >= 0; i--)if (gr[y][i] != gr[x][i])x = gr[x][i], y = gr[y][i];
    return gr[x][0];
}

int build(int l = 1, int r = sv) {
    if (l == r)return cnt++;
    int p = cnt++, mid = (l + r) >> 1;
    node[p].l = build(l, mid), node[p].r = build(mid + 1, r), node[p].v = 0;
    return p;
}

int query(int lca, int a, int b, int k, int obj, int l = 1, int r = sv) {//这里需要特别注意，三棵主席树同时转移
    if (l == r)return tmp[l];
    int mid = (l + r) >> 1;
    int p = node[node[b].l].v + node[node[a].l].v - 2 * node[node[lca].l].v +
            (obj <= mid && obj >= l ? 1 : 0);//注意计入lca的点权，函数中用obj表示其离散化结果
    if (p >= k)return query(node[lca].l, node[a].l, node[b].l, k, obj, l, mid);
    return query(node[lca].r, node[a].r, node[b].r, k - p, obj, mid + 1, r);
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> v[i];
        tmp[i] = v[i];
    }
    for (int i = 1, x, y; i < n; i++) {
        cin >> x >> y;
        add(x, y), add(y, x);
    }
    sort(tmp + 1, tmp + n + 1), sv = unique(tmp + 1, tmp + n + 1) - tmp - 1;
    root[0] = build(), dep[1] = 1, DFS(1, 0);
    while (m--) {
        int a, b, c, lca;
        cin >> a >> b >> c;
        lca = LCA(a, b);
        printf("%d\n", ans = query(root[lca], root[a], root[b], c, lower_bound(tmp + 1, tmp + sv + 1, v[lca]) - tmp));
    }
    return 0;
}

对主席树的进一步理解

        仅仅会用主席树解决区间第k小问题是远远不够的，我们应该从一个更高的层次去理解主席树。
        主席树本质上是很多权值线段树，实质上同时维护了很多数的前缀个数和，这使得我们可以在低复杂度下求任何一个数在某一段区间中出现的次数，这一点十分有用，能解决很多实际问题，第k小只是其中之一。
        也就是说，凡是涉及求任何一种数在区间中出现的次数时，都可以套一下主席树。想象一下，现在有一个$10^5$量级的数组，如果那数组维护每一种数的前缀个数，这样连数组都开不动，现在就可以拿主席树解决了。
        支持单点修改的树状数组套主席树更加有用，比如说，它可以帮助我们求动态逆序对。看这样一道题：洛谷P3157。
        当从原序列中删去一个数时，需要考虑其对答案的影响。这个影响显然就是它前面比它大的数的数目以及它后面比其小的数的数目。这里涉及求某一区间数的次数问题，就可以拿主席树解决。又因为需要将这个数去除，需要单点修改，于是用树状数组套主席树也就理所应当了。

可持久化数组

下面就可以来认识真正的一种可持久化：可持久化数组。模板题。
可持久化数组就是支持查询修改历史版本的数组，可以用主席树实现。这里的主席树其实只有叶子结点的权值有效，它们储存对应的数组中的值。直接来看初始化和构树算法：

int build(int l, int r) {
    int rt = cnt++;
    if (l < r)L[rt] = build(l, (l + r) >> 1), R[rt] = build(((l + r) >> 1) + 1, r);
    else V[rt] = op[l];//记录点权
    return rt;
}

int newTree(int l, int r, int pre, int s, int what) {//把s位置的值改成what
    int rt = cnt++;
    L[rt] = L[pre], R[rt] = R[pre];
    if (l < r) {
        if (s > ((l + r) >> 1))R[rt] = newTree(((l + r) >> 1) + 1, r, R[pre], s, what);
        else L[rt] = newTree(l, (l + r) >> 1, L[pre], s, what);
    } else V[rt] = what;//把值改成what
    return rt;
}

查询过程：

int query(int k, int a, int b, int rk) {
    if (a == b)return V[rk];//直接返回权值
    if (((a + b) >> 1) < k)return query(k, ((a + b) >> 1) + 1, b, R[rk]);
    return query(k, a, ((a + b) >> 1), L[rk]);
}

由于每一个操作都对应一个版本，所以我们需要用一个数组来储存版本所对应的根结点标号，这个很容易实现。全代码如下：

#include<bits/stdc++.h>

#define N 1000005
using namespace std;

inline int read() {
    char e = getchar();
    int s = 0, p = 0;
    while (e < '-')e = getchar();
    if (e == '-')p = 1, e = getchar();
    while (e > '-')s = (s << 1) + (s << 3) + (e & 15), e = getchar();
    return p ? -s : s;
}

int n, q, m, L[N << 6], R[N << 6], V[N << 6], op[N], tmp[N], root[N], cnt = 1, v, a, b, c, ver[N];
int root_cnt = 1;

int build(int l, int r) {
    int rt = cnt++;
    if (l < r)L[rt] = build(l, (l + r) >> 1), R[rt] = build(((l + r) >> 1) + 1, r);
    else V[rt] = op[l];
    return rt;
}

int newTree(int l, int r, int pre, int s, int what) {
    int rt = cnt++;
    L[rt] = L[pre], R[rt] = R[pre];
    if (l < r) {
        if (s > ((l + r) >> 1))R[rt] = newTree(((l + r) >> 1) + 1, r, R[pre], s, what);
        else L[rt] = newTree(l, (l + r) >> 1, L[pre], s, what);
    } else V[rt] = what;
    return rt;
}

int query(int k, int a, int b, int rk) {
    if (a == b)return V[rk];
    if (((a + b) >> 1) < k)return query(k, ((a + b) >> 1) + 1, b, R[rk]);
    return query(k, a, ((a + b) >> 1), L[rk]);
}

int main() {
    n = read(), q = read();
    for (int i = 1; i <= n; i++)op[i] = read();
    root[0] = build(1, n), ver[0] = 0;
    for (int i = 1; i <= q; i++) {
        v = read(), a = read();
        if (a == 1)b = read(), c = read(), root[root_cnt] = newTree(1, n, root[ver[v]], b, c), ver[i] = root_cnt++;
        else a = read(), printf("%d\n", query(a, 1, n, root[ver[v]])), ver[i] = ver[v];
    }
    return 0;
}

可持久化并查集

有了可持久化数组，就可以实现可持久化并查集。
由于维护并查集其实就是维护一个father数组，可以利用可持久化数组的方法实现。代码如下（会TLE）：

#include<bits/stdc++.h>

#define N 1000005
using namespace std;

inline int read() {
    char e = getchar();
    int s = 0, p = 0;
    while (e < '-')e = getchar();
    if (e == '-')p = 1, e = getchar();
    while (e > '-')s = (s << 1) + (s << 3) + (e & 15), e = getchar();
    return p ? -s : s;
}

int n, q, L[N << 6], R[N << 6], fa[N << 6], root[N], cnt = 1, now, a, b, c, ver[N];
int root_cnt = 1;

int build(int l, int r) {
    int rt = cnt++;
    if (l < r)L[rt] = build(l, (l + r) >> 1), R[rt] = build(((l + r) >> 1) + 1, r);
    else fa[rt] = l;//fa初始化
    return rt;
}

int newTree(int l, int r, int pre, int s, int what) {
    int rt = cnt++;
    L[rt] = L[pre], R[rt] = R[pre];
    if (l < r) {
        if (s > ((l + r) >> 1))R[rt] = newTree(((l + r) >> 1) + 1, r, R[pre], s, what);
        else L[rt] = newTree(l, (l + r) >> 1, L[pre], s, what);
    } else fa[rt] = what;
    return rt;
}

int query(int k, int a, int b, int rk) {
    if (a == b)return rk;
    if (((a + b) >> 1) < k)return query(k, ((a + b) >> 1) + 1, b, R[rk]);
    return query(k, a, ((a + b) >> 1), L[rk]);
}

int findF(int x, int v) {
    int f = query(fa[x], 1, n, v);//这一步很重要，要找到对应树上的对应结点
    if (f == x)return fa[x];
    return findF(f, v);
}

int main() {
    int x, y;
    n = read(), q = read();
    root[0] = build(1, n), ver[0] = 0, now = 0;
    for (int i = 1; i <= q; i++) {
        a = read();
        if (a == 1) {
            b = read(), c = read();
            x = findF(query(b, 1, n, root[ver[now]]), root[ver[now]]);
            y = findF(query(c, 1, n, root[ver[now]]), root[ver[now]]);
            if (x != y)root[root_cnt] = newTree(1, n, root[ver[now]], x, y), ver[i] = root_cnt++;
            else ver[i] = ver[now];
        } else if (a == 2)ver[i] = ver[read()];
        else {
            b = read(), c = read();
            x = findF(query(b, 1, n, root[ver[now]]), root[ver[now]]);
            y = findF(query(c, 1, n, root[ver[now]]), root[ver[now]]);
            printf("%d\n", x == y), ver[i] = ver[now];
        }
        now = i;
    }
    return 0;
}

        仍然是只利用线段树的叶子结点点权。它们只有一个权值，即father（代码中用fa），记录它的父结点的值（不是结点编号！！）。但这样在找father时会出现一个问题，那就是有很多历史版本，那就有很多值相同的结点，到底那个才是？当然选择在同一个版本下的结点，所以这里在找father时需要查询。这里容易混淆值和编号。
        上面的算法会TLE，原因显然：没有路径压缩，找father过程能直接卡到O(n)。在可持久化并查集中，我们不能进行路径压缩，这是因为路径压缩会破坏原有历史版本的信息，需要另辟蹊径。那么并查集除了路径压缩还有什么方法可以加快找father的速度？应选择按秩合并。
        按秩合并很容易理解。用deep指标记录每一个等价类树的深度，那么当两个深度不等的树合并时，应将深度较小的合并到深度较大的树上，这样可以保证深度增长尽可能小。如果两者深度相同，那么合并后的树根深度需要加一。

inline void merge(int x, int y) {
    if (deep[x] > deep[y])swap(x, y);
    root[root_cnt] = newTree(1, n, root[ver[now]], fa[x], fa[y]);//修改fa[x]位置结点的father为fa[y]
    if (deep[x] == deep[y])deep[query(fa[y], 1, n, root[root_cnt])]++;//直接修改深度
}

上面是可持久化并查集的合并函数。由于只有树根的deep才有用，所以只需要修改树根的deep即可。这里可能会有一个疑问：为什么只需要修改而不是新建结点？深度并不是我们需要维护的历史信息，因此修改这一个“历史信息”并不会带来实质性的影响。

#include<bits/stdc++.h>

#define N 1000005
using namespace std;

inline int read() {
    char e = getchar();
    int s = 0, p = 0;
    while (e < '-')e = getchar();
    if (e == '-')p = 1, e = getchar();
    while (e > '-')s = (s << 1) + (s << 3) + (e & 15), e = getchar();
    return p ? -s : s;
}

int n, q, L[N << 6], R[N << 6], fa[N << 6], root[N], cnt = 1, now, a, b, c, ver[N], deep[N<<6];
int root_cnt = 1;

int build(int l, int r) {
    int rt = cnt++;
    if (l < r)L[rt] = build(l, (l + r) >> 1), R[rt] = build(((l + r) >> 1) + 1, r);
    else fa[rt] = l, deep[rt] = 1;//注意初始化deep
    return rt;
}

int newTree(int l, int r, int pre, int s, int what) {
    int rt = cnt++;
    L[rt] = L[pre], R[rt] = R[pre];
    if (l < r) {
        if (s > ((l + r) >> 1))R[rt] = newTree(((l + r) >> 1) + 1, r, R[pre], s, what);
        else L[rt] = newTree(l, (l + r) >> 1, L[pre], s, what);
    } else fa[rt] = what, deep[rt] = deep[pre];//继承原版本的deep值
    return rt;
}

int query(int k, int a, int b, int rk) {
    if (a == b)return rk;
    if (((a + b) >> 1) < k)return query(k, ((a + b) >> 1) + 1, b, R[rk]);
    return query(k, a, ((a + b) >> 1), L[rk]);
}

int findF(int x, int v) {
    int f = query(fa[x], 1, n, v);
    if (f == x)return x;
    return findF(f, v);
}

inline void merge(int x, int y) {
    if (deep[x] > deep[y])swap(x, y);
    root[root_cnt] = newTree(1, n, root[ver[now]], fa[x], fa[y]);
    if (deep[x] == deep[y])deep[query(fa[y], 1, n, root[root_cnt])]++;
}

int main() {
    int x, y;
    n = read(), q = read();
    root[0] = build(1, n), ver[0] = 0, now = 0;
    for (int i = 1; i <= q; i++) {
        a = read();
        if (a == 1) {
            b = read(), c = read();
            x = findF(query(b, 1, n, root[ver[now]]), root[ver[now]]);
            y = findF(query(c, 1, n, root[ver[now]]), root[ver[now]]);
            if (fa[x] != fa[y]) merge(x, y), ver[i] = root_cnt++;
            else ver[i] = ver[now];
        } else if (a == 2)ver[i] = ver[read()];
        else {
            b = read(), c = read();
            x = findF(query(b, 1, n, root[ver[now]]), root[ver[now]]);
            y = findF(query(c, 1, n, root[ver[now]]), root[ver[now]]);
            printf("%d\n", x == y), ver[i] = ver[now];
        }
        now = i;
    }
    return 0;
}