首页 > 其他分享 >P3402 可持久化并查集

P3402 可持久化并查集

时间:2022-10-07 20:23:33浏览次数:80  
标签:rt P3402 持久 int 查集 fa posx posy pos1

P3402

通过主席树维护不同版本的并查集,注意要采用按秩合并的方式,路径压缩可能会爆。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int N = 3e5 + 10;
 4 int n, m, rt[N * 30];
 5 struct node {
 6     int ls, rs, dep, fa;//fa的值都是在1~n范围中的 
 7 }t[N * 30]; 
 8 namespace SegmentTree {
 9     #define mid ((l + r) >> 1)
10     #define lson t[i].ls, l, mid
11     #define rson t[i].rs, mid + 1, r
12     int cnt;
13     void build(int &i, int l, int r) {
14         i = ++ cnt;
15         if (l == r) {t[i].fa = l; return ;}//初始时节点父亲就是自己
16         build(lson), build(rson); 
17     }
18     void merge(int j, int &i, int l, int r, int pos1, int pos2) {
19         //pos1是深度较小的节点的fa,找到pos1的位置,将该位置的fa改为pos2,也就是合并操作 
20         i = ++ cnt;
21         t[i] = t[j];//复制 
22         if (l == r) {
23             t[i].fa = pos2;
24             return ;
25         }
26         if (pos1 <= mid) merge(t[j].ls, lson, pos1, pos2);
27         else merge(t[j].rs, rson, pos1, pos2);
28     }
29     void update(int i, int l, int r, int pos) {
30         if (l == r) {t[i].dep ++; return ;}
31         if (pos <= mid) update(lson, pos);
32         else update(rson, pos);
33     }
34     int query(int i, int l, int r, int pos) {//返回节点pos的编号 
35         if (l == r) return i;
36         if (pos <= mid) return query(lson, pos);
37         else return query(rson, pos);
38     }
39     int find(int i, int pos) {//类似并查集找祖先操作 
40         int now = query(i, 1, n, pos);
41         if (t[now].fa == pos) return now;//也是返回节点编号 
42         return find(i, t[now].fa);
43     }
44     #undef mid
45     #undef lson
46     #undef rson
47 }
48 using namespace SegmentTree;
49 int main() {
50     scanf("%d %d", &n, &m);
51     build(rt[0], 1, n);
52     for (int i = 1; i <= m; i ++) {
53         int opt, x, y;
54         scanf("%d %d", &opt, &x);
55         if(opt == 1) {//合并x, y所在集合 
56             scanf("%d", &y);
57             int posx, posy;
58             rt[i] = rt[i - 1];//复制新版本
59             posx = find(rt[i], x), posy = find(rt[i], y);
60             if (t[posx].fa != t[posy].fa) {//按秩合并 
61                 if (t[posx].dep > t[posy].dep) swap(posx, posy);
62                 merge(rt[i - 1], rt[i], 1, n, t[posx].fa, t[posy].fa);
63                 if (t[posx].dep == t[posy].dep) update(rt[i], 1, n, t[posy].fa);
64                 //避免深度相同 
65             } 
66         }
67         else if(opt == 2) rt[i] = rt[x];
68         else if(opt == 3) {
69             scanf("%d", &y);
70             rt[i] = rt[i - 1];
71             int posx, posy;
72             posx = find(rt[i], x), posy = find(rt[i], y);
73             if (t[posx].fa == t[posy].fa) puts("1");
74             else puts("0");
75         }
76     }
77     return 0;
78 }

 

标签:rt,P3402,持久,int,查集,fa,posx,posy,pos1
From: https://www.cnblogs.com/YHxo/p/16760609.html

相关文章

  • P3919 【模板】可持久化线段树 1(可持久化数组)
    还是用主席树来做(因为提到不同的版本),这时候的主席树不是以权值为下标的,就是普通的线段树,维护范围1~n,i存的是a[]中的数。1#include<bits/stdc++.h>2usingnamespac......
  • KAL1 LINUX 官方文档之usb live版本 --- 将持久性添加到 Kali Linux Live USB 驱动器
    将持久性添加到KaliLinuxLiveUSB驱动器KaliLinux“Live”在默认启动菜单中有两个选项可以启用持久性——在“KaliLive”USB驱动器上保存数据——在“KaliLive”......
  • KAL1 LINUX 官方文档之usb live版本 --- 将加密持久性添加到 Kali Linux Live USB 驱
    将加密持久性添加到KaliLinuxLiveUSB驱动器在本次研讨会中,我们将研究从USB设备启动KaliLinux时可用的各种功能。我们将探索诸如持久性、创建LUKS加密持久性......
  • 【持久层框架】- SpringData - JPA
    JPA简介JPA即JavaPersistenceAPI。是一款持久层框架,中文名Java持久层API,是JDK5.0注解或XML描述对象-关系表的映射关系,并将运行期的实体对象持久化到数据库中。JPA的对象......
  • redis的两种持久化方式
    redis的两种持久化方式redis是一个内存数据库,一旦断电或服务器进程退出,内存数据库中的数据将全部丢失,所以需要redis持久化redis持久化就是把数据保存在磁盘上,利用永久性......
  • Redis之持久化存储
    Redis持久化解决方案RDBRDB存储的重点在于数据本身,将数据持久化存入后缀为.rdb的文件中,即快照,每隔一段时间记录新的数据,像快速拍照一样,每次拍完放在一边,用的时候快速......
  • P3834 【模板】可持久化线段树 2
    P3834主席树模板,求区间第k小。1#include<bits/stdc++.h>2usingnamespacestd;3#definelctr[i].ch[0]4#definerctr[i].ch[1]5#defineLctr[j].ch[0......
  • 并查集应用 matlab
    ​有lun文和源码群 1160391469并查集是一种用来管理分组情况的数据结构,可以高效的查询元素a,元素b是否来自于一组。并且可以合并元素a和元素b所在的组。虽然并查集可以......
  • CF1681F. Unique Occurrences (可撤销并查集, 分治)
    https://codeforces.com/contest/1681/problem/F题意:给5e5节点的树,问所有路径的贡献和,一条路径的贡献指路径上上只出现一次的边权的个数。思路:对于每种边权的贡献:对于边......
  • Redis高可用(持久化、主从复制、哨兵、集群)
    Redis高可用(持久化、主从复制、哨兵、集群)一、Redis高可用1.Redis高可用概述在web服务器中,高可用是指服务器可以正常访问的时间,衡量的标准是在多长时间内可以提供正常......