社区讨论

有大佬能帮忙看看我Splay和Rotate两个操作有问题吗?

P3690【模板】动态树(LCT)参与者 4已保存回复 6

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
6 条
当前快照
1 份
快照标识符
@mi7w220n
此快照首次捕获于
2025/11/21 04:33
4 个月前
此快照最后确认于
2025/11/21 04:33
4 个月前
查看原帖
交上去只有十分,经过初步筛选,发现问题出在Splay和Rotate,但是我太菜了,调了半天也没觉得哪儿有错,麻烦诸位了
CPP
#include<bits/stdc++.h>
const int N=300005;
using namespace std;
template<class T>
inline void read(T &x)
{
    x=0; int f=1;
    static char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    x*=f;
}
struct Link_Cut_Tree
{
    int lc,rc,fa,val,f;
}t[N];
int n,m,val[N];
inline bool isroot(int u){return t[t[u].fa].lc!=u&&t[t[u].fa].rc!=u;}
inline void pushup(int u){t[u].val=t[t[u].lc].val^t[t[u].rc].val^val[u];}
inline void pushnow(int u)
{
	swap(t[u].lc,t[u].rc);
	t[u].f^=1;
}
inline void pushdown(int u){//判断并释放懒标记
    if(t[u].f){
        if(t[u].lc) pushnow(t[u].lc);
        if(t[u].rc) pushnow(t[u].rc);
        t[u].f=0;
    }
}
inline int which(int u){return t[t[u].fa].rc==u;}
inline void Rotate(int u)
{
    int v=t[u].fa,w=t[v].fa;
    int b=(t[v].rc==u)?t[u].lc:t[u].rc;
    t[u].fa=w; t[v].fa=u;	
    if(b) t[b].fa=v;
    if(!isroot(v)) (t[w].lc==v?t[w].lc:t[w].rc)=u;
    if(u==t[v].rc)	t[u].lc=v,t[v].rc=b;
    else t[u].rc=v,t[v].lc=b;
    pushup(v); pushup(u);
}
int sta[N];
inline void Splay(int u)
{
    int v=u,top=0;
    sta[++top]=v;
    while(!isroot(v)) sta[++top]=v=t[v].fa;
    while(top) pushdown(sta[top--]);
    while(!isroot(u))
    {
        if(!isroot(t[u].fa))
        {
            if(which(t[u].fa)==which(t[t[u].fa].fa))	Rotate(t[u].fa);
            else Rotate(u);
        }
        Rotate(u);
    }
}
inline void access(int u)
{
    for(int v=0;u;u=t[v=u].fa)
        Splay(u),puts("ALIVE"),t[u].rc=v,pushup(u);
}
inline void makeroot(int u){access(u); Splay(u); pushnow(u);}	
inline void Split(int u,int v){makeroot(u); access(v); Splay(v);}
inline int find(int u)
{
    access(u); Splay(u);
    while(t[u].lc) pushdown(u),u=t[u].lc;
    Splay(u);
    return u;
}
inline void Link(int u,int v){makeroot(u); if(find(v)!=u) t[u].fa=v;}
inline void Cut(int u,int v)
{
    makeroot(u);
    if(find(v)==u&&t[v].fa==u&&t[v].lc==0) 
        t[v].fa=t[u].rc=0,pushup(u);
}
int main()
{
    read(n),read(m);
    for(int i=1;i<=n;i++) read(val[i]);
    int opt,x,y;
    while(m--)
    {
        read(opt); read(x); read(y);
        if(opt==0)	Split(x,y),printf("%d\n",t[y].val);
        if(opt==1)	Link(x,y);
        if(opt==2)	Cut(x,y);
        if(opt==3)	Splay(x),val[x]=y;
    }
    return 0;
}

回复

6 条回复,欢迎继续交流。

正在加载回复...