当前位置:网站首页>P3402 persistent and searchable
P3402 persistent and searchable
2022-07-03 19:14:00 【It's Alpaca duck】
Topic link : Click here
The main idea of the topic :
Given n n n A collection of , The first i i i There is only one number in the initial state in a set , by i i i.
Yes m m m operations . The operation is divided into 3 3 3 Kind of :
1 a b 1\ a\ b 1 a b Merge a , b a,b a,b In the collection ;
2 k 2\ k 2 k Back to the first k k k operations ( Performing any of the three operations is recorded as an operation ) The state after ;
3 a b 3\ a\ b 3 a b inquiry a , b a,b a,b Whether they belong to the same set , Output if yes 1 1 1 , Otherwise output 0 0 0.
For each operation 3 3 3, Output an integer on a line to represent the answer
Topic analysis :
Use the chairman tree to build a persistent array to serve as the array subscript of the original union search set , For the search operation that the search subscript directly corresponds to the persistent array
The idea of rank based merging is needed to perform the merging operation to ensure the time complexity , The reason for not using path compression is that using path compression may make it easy for updates to generate a lot of redundant space M L E MLE MLE
See code for details :
// Problem: P3402 Persistent and searchable
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3402
// Memory Limit: 125 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
//#pragma GCC optimize(2)
//#pragma GCC optimize("Ofast","inline","-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<unordered_map>
#define ll long long
#define inf 0x3f3f3f3f
#define Inf 0x3f3f3f3f3f3f3f3f
//#define int ll
#define endl '\n'
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
using namespace std;
int read()
{
int res = 0,flag = 1;
char ch = getchar();
while(ch<'0' || ch>'9')
{
if(ch == '-') flag = -1;
ch = getchar();
}
while(ch>='0' && ch<='9')
{
res = (res<<3)+(res<<1)+(ch^48);//res*10+ch-'0';
ch = getchar();
}
return res*flag;
}
const int maxn = 1e6+5;
const int mod = 1e9+7;
const double pi = acos(-1);
const double eps = 1e-8;
struct node{
int l,r;
}nod[maxn*32];
int n,m,cnt,root[maxn],fa[maxn*32],dep[maxn*32];
void build(int &u,int l,int r)
{
nod[u = ++cnt];
if(l == r)
{
fa[u] = l;
return ;
}
int mid = l+r>>1;
build(nod[u].l,l,mid);
build(nod[u].r,mid+1,r);
}
int query(int u,int l,int r,int pos)
{
if(l == r) return u;
int mid = l+r>>1;
if(pos <= mid) return query(nod[u].l,l,mid,pos);
else return query(nod[u].r,mid+1,r,pos);
}
int find(int root,int x)
{
int pos = query(root,1,n,x);
if(fa[pos] == x) return pos;
return find(root,fa[pos]);
}
void update(int &u,int pre,int l,int r,int pos,int fax) // modify pos My father is fax
{
nod[u = ++cnt];
if(l == r)
{
fa[u] = fax;
dep[u] = dep[pre];
return ;
}
int mid = l+r>>1;
nod[u].l = nod[pre].l;
nod[u].r = nod[pre].r;
if(pos <= mid) update(nod[u].l,nod[pre].l,l,mid,pos,fax);
else update(nod[u].r,nod[pre].r,mid+1,r,pos,fax);
}
void add(int u,int l,int r,int pos) // Add one to the root depth of a union search set
{
if(l == r)
{
dep[u]++;
return ;
}
int mid = l+r>>1;
if(pos <= mid) add(nod[u].l,l,mid,pos);
else add(nod[u].r,mid+1,r,pos);
}
int main()
{
n = read(),m = read();
build(root[0],1,n);
for(int i = 1;i <= m;i++)
{
int opt = read();
if(opt == 1)
{
int x = read(),y = read();
root[i] = root[i-1];
int px = find(root[i],x),py = find(root[i],y);
if(fa[px] == fa[py]) continue;
if(dep[px] > dep[py]) swap(px,py);
update(root[i],root[i-1],1,n,fa[px],fa[py]);
if(dep[px] == dep[py]) add(root[i],1,n,fa[py]); // Note that fa[py], Because the new root at this time is fa[py], The depth is increased 1
}
else if(opt == 2)
{
int id = read();
root[i] = root[id];
}
else if(opt == 3)
{
int x = read(),y = read();
root[i] = root[i-1];
int fax = find(root[i],x),fay = find(root[i],y);
puts(fax==fay ? "1" : "0");
}
}
return 0;
}
边栏推荐
- Using the visualization results, click to appear the corresponding sentence
- Latex image rotates with title
- 2020 intermediate financial management (escort class)
- DriveSeg:动态驾驶场景分割数据集
- shell 脚本中关于用户输入参数的处理
- 2022.2.14 Li Kou - daily question - single element in an ordered array
- Web3 credential network project galaxy is better than nym?
- TFs and SVN [closed] - TFs vs SVN [closed]
- Ego planner code parsing Bspline_ Optimizer section (1)
- [optics] dielectric constant calculation based on MATLAB [including Matlab source code 1926]
猜你喜欢
EGO Planner代码解析bspline_optimizer部分(2)
【学术相关】顶级论文创新点怎么找?中国高校首次获CVPR最佳学生论文奖有感...
Using the visualization results, click to appear the corresponding sentence
Simulation scheduling problem of SystemVerilog (1)
If the warehouse management communication is not in place, what problems will occur?
SSM integration - joint debugging of front and rear protocols (list function, add function, add function status processing, modify function, delete function)
235. Ancêtre public le plus proche de l'arbre de recherche binaire [modèle LCA + même chemin de recherche]
How to build an efficient information warehouse
【光学】基于matlab介电常数计算【含Matlab源码 1926期】
Smart wax therapy machine based on STM32 and smart cloud
随机推荐
Hard disk monitoring and analysis tool: smartctl
Simulation scheduling problem of SystemVerilog (1)
leetcode:556. Next larger element III [simulation + change as little as possible]
Zhengda futures news: soaring oil prices may continue to push up global inflation
User identity used by startup script and login script in group policy
Thesis study - 7 Very Deep Convolutional Networks for Large-Scale Image Recognition (3/3)
TFs and SVN [closed] - TFs vs SVN [closed]
Ego planner code parsing Bspline_ Optimizer section (3)
HOW TO WRITE A DAILY LAB NOTE?
High concurrency architecture cache
Record: pymysql is used in pycharm to connect to the database
These problems should be paid attention to in the production of enterprise promotional videos
What is the content of game modeling
Introduction to SSH Remote execution command
“google is not defined” when using Google Maps V3 in Firefox remotely
利用可视化结果,点击出现对应的句子
【LeetCode】【SQL】刷题笔记
Sqlalchemy - subquery in a where clause - Sqlalchemy - subquery in a where clause
Find the median of two positive arrays
【光学】基于matlab介电常数计算【含Matlab源码 1926期】