当前位置:网站首页>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;
}
边栏推荐
- [new year job hopping season] test the technical summary of interviewers' favorite questions (with video tutorials and interview questions)
- “google is not defined” when using Google Maps V3 in Firefox remotely
- Think of new ways
- [leetcode] [SQL] notes
- Redis master-slave synchronization, clustering, persistence
- [disease identification] machine vision lung cancer detection system based on Matlab GUI [including Matlab source code 1922]
- Work Measurement - 1
- ActiveMQ的基础
- Integrated easy to pay secondary domain name distribution system
- Webrtc[41] - Analysis of the establishment process of webrtc transmission channel
猜你喜欢
Merge K ascending linked lists
Help change the socket position of PCB part
SSM integration - joint debugging of front and rear protocols (list function, add function, add function status processing, modify function, delete function)
This Chinese numpy quick look-up table is too easy!
Record: pymysql is used in pycharm to connect to the database
leetcode:11. 盛最多水的容器【雙指針 + 貪心 + 去除最短板】
Dart JSON编码器和解码器剖析
The online customer service system developed by PHP is fully open source without encryption, and supports wechat customer service docking
235. The nearest common ancestor of the binary search tree [LCA template + same search path]
Zhengda futures news: soaring oil prices may continue to push up global inflation
随机推荐
I didn't cancel
Using the visualization results, click to appear the corresponding sentence
Record: writing MySQL commands
Floating source code comment (38) parallel job processor
SQL: special update operation
Comments on flowable source code (37) asynchronous job processor
Scrapy爬虫框架
SSM整合-前后台协议联调(列表功能、添加功能、添加功能状态处理、修改功能、删除功能)
Introduction to SSH Remote execution command
變化是永恒的主題
Flask generates swagger documents
The way to treat feelings
Analysis of dart JSON encoder and decoder
Change is the eternal theme
leetcode:556. 下一个更大元素 III【模拟 + 尽可能少变更】
The installation path cannot be selected when installing MySQL 8.0.23
Valentine's Day - make an exclusive digital collection for your lover
【光学】基于matlab涡旋光产生【含Matlab源码 1927期】
Max of PHP FPM_ Some misunderstandings of children
Which do MySQL and Oracle learn?