好奇：关于按size合并与按depth合并时间复杂度的区别
- 板块P3402 可持久化并查集
- 楼主liu_chen_hao
- 当前回复4
- 已保存回复4
- 发布时间2023/7/24 16:29
- 上次更新2023/11/3 07:53:48
查看原帖
被骇客银狼阻止的越权访问保存失败
好奇：关于按size合并与按depth合并时间复杂度的区别
RT，我按照size合并，TLE83分，其他的没改，改成按depth合并就AC了，想问问各位大佬，这二者的复杂度不应该都可以证明是 O(logn) 的吗，为何按深度合并远远快于按大小合并？
按size合并的TLE代码：
#include <bits/stdc++.h>
#define debug cout<<"zzy AK lch\n";
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define mp make_pair
#define b_s basic_string
#define fir first
#define sec second
#define ll long long
#define ull unsigned long long
#define ld long double
using namespace std;
const int N=3e5+5,M=3e5+5,T=1e7+5;
const int mod=998244353;
const int inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3f;
struct nod {
int ls,rs,s;
}t1[T],t2[T];
int n,m,tot1,tot2;
int rt1[M],rt2[M];
int read() {
int sss=0,www=1;
char ccch=getchar();
while(ccch<'0' || ccch>'9') { if(ccch=='-') www=-1; ccch=getchar(); }
while(ccch>='0' && ccch<='9') sss=sss*10+ccch-'0',ccch=getchar();
return sss*www;
}
void Add(ll &xcr, ll zzy) { xcr=(xcr+zzy)%mod; }
void build1(int &p, int l, int r)
{
if(!p) p=++tot1;
if(l==r)
{
t1[p].s=l;
return;
}
int mid=((l+r)>>1);
build1(t1[p].ls,l,mid);
build1(t1[p].rs,mid+1,r);
}
void modify1(int &u, int v, int L, int R, int p, int x)
{
if(!u) u=++tot1;
if(L==R)
{
t1[u].s=x;
return;
}
int mid=((L+R)>>1);
if(p<=mid)
{
t1[u].rs=t1[v].rs;
modify1(t1[u].ls,t1[v].ls,L,mid,p,x);
}
else
{
t1[u].ls=t1[v].ls;
modify1(t1[u].rs,t1[v].rs,mid+1,R,p,x);
}
}
int query1(int u, int L, int R, int p)
{
if(L==R) return t1[u].s;
int mid=((L+R)>>1);
if(p<=mid) return query1(t1[u].ls,L,mid,p);
return query1(t1[u].rs,mid+1,R,p);
}
void build2(int &p, int l, int r)
{
if(!p) p=++tot2;
if(l==r)
{
t2[p].s=1;
return;
}
int mid=((l+r)>>1);
build2(t2[p].ls,l,mid);
build2(t2[p].rs,mid+1,r);
}
void modify2(int &u, int v, int L, int R, int p, int x)
{
if(!u) u=++tot2;
if(L==R)
{
t2[u].s=t2[v].s+x; // 这里不一样
return;
}
int mid=((L+R)>>1);
if(p<=mid)
{
t2[u].rs=t2[v].rs;
modify2(t2[u].ls,t2[v].ls,L,mid,p,x);
}
else
{
t2[u].ls=t2[v].ls;
modify2(t2[u].rs,t2[v].rs,mid+1,R,p,x);
}
}
int query2(int u, int L, int R, int p)
{
if(L==R) return t2[u].s;
int mid=((L+R)>>1);
if(p<=mid) return query2(t2[u].ls,L,mid,p);
return query2(t2[u].rs,mid+1,R,p);
}
int find(int u, int x) {
int fa=query1(u,1,n,x);
if(fa==x) return x;
return find(u,fa);
}
int main()
{
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
//ios::sync_with_stdio(false);
n=read(),m=read();
// for(int i=1; i<=n; i++) fa[i]=i,siz[i]=1;
build1(rt1[0],1,n);
build2(rt2[0],1,n);
for(int i=1,op,a,b,x,fa,fb,sa,sb; i<=m; i++)
{
op=read();
if(op==1)
{
a=read(),b=read();
fa=find(rt1[i-1],a);
fb=find(rt1[i-1],b);
if(fa==fb)
{
rt1[i]=rt1[i-1];
rt2[i]=rt2[i-1];
continue;
}
sa=query2(rt2[i-1],1,n,fa);
sb=query2(rt2[i-1],1,n,fb);
if(sa>sb) swap(fa,fb);
modify1(rt1[i],rt1[i-1],1,n,fa,fb);
modify2(rt2[i],rt2[i-1],1,n,fb,sa); // 这里不一样
}
else if(op==2)
{
x=read();
rt1[i]=rt1[x],rt2[i]=rt2[x];
}
else
{
rt1[i]=rt1[i-1],rt2[i]=rt2[i-1];
a=read(),b=read();
fa=find(rt1[i],a),fb=find(rt1[i],b);
if(fa==fb) printf("1\n");
else printf("0\n");
}
}
return 0;
}
这是按depth合并的AC代码：
#include <bits/stdc++.h>
#define debug cout<<"zzy AK lch\n";
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define mp make_pair
#define b_s basic_string
#define fir first
#define sec second
#define ll long long
#define ull unsigned long long
#define ld long double
using namespace std;
const int N=3e5+5,M=3e5+5,T=1e7+5;
const int mod=998244353;
const int inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3f;
struct nod {
int ls,rs,s;
}t1[T],t2[T];
int n,m,tot1,tot2;
int rt1[M],rt2[M];
int read() {
int sss=0,www=1;
char ccch=getchar();
while(ccch<'0' || ccch>'9') { if(ccch=='-') www=-1; ccch=getchar(); }
while(ccch>='0' && ccch<='9') sss=sss*10+ccch-'0',ccch=getchar();
return sss*www;
}
void Add(ll &xcr, ll zzy) { xcr=(xcr+zzy)%mod; }
void build1(int &p, int l, int r)
{
if(!p) p=++tot1;
if(l==r)
{
t1[p].s=l;
return;
}
int mid=((l+r)>>1);
build1(t1[p].ls,l,mid);
build1(t1[p].rs,mid+1,r);
}
void modify1(int &u, int v, int L, int R, int p, int x)
{
if(!u) u=++tot1;
if(L==R)
{
t1[u].s=x;
return;
}
int mid=((L+R)>>1);
if(p<=mid)
{
t1[u].rs=t1[v].rs;
modify1(t1[u].ls,t1[v].ls,L,mid,p,x);
}
else
{
t1[u].ls=t1[v].ls;
modify1(t1[u].rs,t1[v].rs,mid+1,R,p,x);
}
}
int query1(int u, int L, int R, int p)
{
if(L==R) return t1[u].s;
int mid=((L+R)>>1);
if(p<=mid) return query1(t1[u].ls,L,mid,p);
return query1(t1[u].rs,mid+1,R,p);
}
void build2(int &p, int l, int r)
{
if(!p) p=++tot2;
if(l==r)
{
t2[p].s=1;
return;
}
int mid=((l+r)>>1);
build2(t2[p].ls,l,mid);
build2(t2[p].rs,mid+1,r);
}
void modify2(int &u, int v, int L, int R, int p, int x)
{
if(!u) u=++tot2;
if(L==R)
{
t2[u].s=max(t2[v].s,x); // 这里不一样
return;
}
int mid=((L+R)>>1);
if(p<=mid)
{
t2[u].rs=t2[v].rs;
modify2(t2[u].ls,t2[v].ls,L,mid,p,x);
}
else
{
t2[u].ls=t2[v].ls;
modify2(t2[u].rs,t2[v].rs,mid+1,R,p,x);
}
}
int query2(int u, int L, int R, int p)
{
if(L==R) return t2[u].s;
int mid=((L+R)>>1);
if(p<=mid) return query2(t2[u].ls,L,mid,p);
return query2(t2[u].rs,mid+1,R,p);
}
int find(int u, int x) {
int fa=query1(u,1,n,x);
if(fa==x) return x;
return find(u,fa);
}
int main()
{
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
//ios::sync_with_stdio(false);
n=read(),m=read();
// for(int i=1; i<=n; i++) fa[i]=i,siz[i]=1;
build1(rt1[0],1,n);
build2(rt2[0],1,n);
for(int i=1,op,a,b,x,fa,fb,da,db; i<=m; i++)
{
op=read();
if(op==1)
{
a=read(),b=read();
fa=find(rt1[i-1],a);
fb=find(rt1[i-1],b);
if(fa==fb)
{
rt1[i]=rt1[i-1];
rt2[i]=rt2[i-1];
continue;
}
da=query2(rt2[i-1],1,n,fa);
db=query2(rt2[i-1],1,n,fb);
if(da>db) swap(fa,fb);
modify1(rt1[i],rt1[i-1],1,n,fa,fb);
modify2(rt2[i],rt2[i-1],1,n,fb,da+1); // 这里不一样
}
else if(op==2)
{
x=read();
rt1[i]=rt1[x],rt2[i]=rt2[x];
}
else
{
rt1[i]=rt1[i-1],rt2[i]=rt2[i-1];
a=read(),b=read();
fa=find(rt1[i],a),fb=find(rt1[i],b);
if(fa==fb) printf("1\n");
else printf("0\n");
}
}
return 0;
}
希望有大佬能给出解答QwQ
加载中...