BZOJ1078: [SCOI2008]斜堆

时间：2021-12-01 20:15:34

题目：http://www.lydsy.com/JudgeOnline/problem.php?id=1078

每一次进入的点一定是一个极左节点，然后将它所处在的整棵树左右翻转。加上一些情况的处理。

#include<cstring>

#include<iostream>

#include<algorithm>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#define rep(i,l,r) for (int i=l;i<=r;i++)

#define down(i,l,r) for (int i=l;i>=r;i--)

#define clr(x,y) memset(x,y,sizeof(x))

#define maxn 2005

#define eps 1e-3

#define ll long long

#define inf (1LL<<50)

using namespace std;

int fa[maxn],l[maxn],r[maxn],ans[maxn],n,tot,root;

int read(){

    int x=,f=; char ch=getchar();

    while (!isdigit(ch)) {if (ch=='-') f=-; ch=getchar();}

    while (isdigit(ch)) {x=x*+ch-''; ch=getchar();}

    return x*f;

}

void solve(){

    int x=root;

    while (r[x]!=-) x=l[x];

    int t=l[x];

    if (t!=-&&l[t]==-&&r[t]==-) x=t;

    ans[++tot]=x;

    if (x==root) root=l[root];

    int f=fa[x];

    if (f!=-) l[f]=l[x],fa[l[f]]=f;

    while (f!=-) swap(l[f],r[f]),f=fa[f];

}

int main(){

    n=read();

    fa[]=-;

    clr(l,-); clr(r,-);

    rep(i,,n) {

        int x=read();

        if (x>=) fa[i]=x-,r[x-]=i;

        else fa[i]=x,l[x]=i;

    }

    rep(i,,n) solve();

    while (tot) printf("%d ",ans[tot--]);

    return ;

}

相关文章