Splay没过，求助

Prean @ 2020-03-01 16:33:57

#include<iostream>
#include<conio.h>
using namespace std;
class splay{public:int f,L,R;bool flag;}t[100005];
int root,n,m,top;
inline void Zig(int x)
{
    int y=t[x].f;t[y].L=t[x].R;
    if(t[x].R)t[t[x].R].f=y;t[x].f=t[y].f;
    if(t[y].f)if(t[t[y].f].L==y)t[t[y].f].L=x;
    else t[t[y].f].R=x;t[x].R=y;t[y].f=x;
}
inline void Zag(int x)
{
    int y=t[x].f;t[y].R=t[x].L;
    if(t[x].L)t[t[x].L].f=y;t[x].f=t[y].f;
    if(t[y].f)if(t[t[y].f].L==y)t[t[y].f].L=x;
    else t[t[y].f].R=x;t[x].L=y;t[y].f=x;
}
inline void Splay(int x,int y)
{
    int p=x;
    while(t[x].f!=y)
    {
        p=t[x].f;
        if(t[p].f==y){if(x==t[p].L)Zig(x);else Zag(x);break;}
        else if(t[p].L==x)if(t[t[p].f].L==p)Zig(p),Zig(x);
        else Zig(x),Zag(x);
        else if(t[t[p].f].L==p)Zag(x),Zig(x);
        else Zag(p),Zag(x);
    }if(!y)root=x;
}
inline void DFS(int f)
{
    if(!f||f==n)return;
    if(t[f].flag){DFS(t[f].R);cout<<f<<" ";DFS(t[f].L);}
    else{DFS(t[f].L);cout<<f<<" ";DFS(t[f].R);}
}
int main()
{
    int i,l,r;ios::sync_with_stdio(false);cin>>n>>m;
    for(i=1;i<=n;++i)t[i].L=i-1,t[i].f=i+1;root=++n;
    t[0].f=1;t[n].L=n-1;
    while(m--)
    {cin>>l>>r;Splay(--l,0);Splay(++r,l);t[t[r].L].flag^=1;}
    DFS(root);
}

by Kubic @ 2020-03-01 16:58:54

@limaopipi2022 第一次看到这样写的Splay

by Prean @ 2020-03-01 17:00:21

@Kubic 这样写也没什么问题呀。。。。。。

by Smile_Cindy @ 2020-03-01 17:06:14

@limaopipi2022

这样写是不对的，翻转的是下标，所以应该这么写。

#include <bits/stdc++.h>
using namespace std;
const int MAX_N=100005;
int ch[MAX_N][2],fa[MAX_N];
int val[MAX_N],cnt[MAX_N],siz[MAX_N];
bool rev[MAX_N];
int n,m,num,rt;
bool idenify(int x)
{
    return ch[fa[x]][1]==x;
}
void update(int x)
{
    siz[x]=siz[ch[x][0]]+cnt[x]+siz[ch[x][1]];
}
void pushdown(int x)
{
    if(rev[x])
    {
        swap(ch[x][0],ch[x][1]);
        rev[ch[x][0]]=!rev[ch[x][0]];
        rev[ch[x][1]]=!rev[ch[x][1]];
        rev[x]=0;
    }
}
void connect(int x,int y,bool flag)
{
    fa[x]=y;
    ch[y][flag]=x;
}
void rotate(int x)
{
    int y=fa[x],z=fa[y];
    bool kx=idenify(x),ky=idenify(y);
    int w=ch[x][!kx];
    connect(w,y,kx);
    connect(x,z,ky);
    connect(y,x,!kx);
    update(y);
    update(x);
}
void splay(int x,int to=0)
{
    while(fa[x]!=to)
    {
        int y=fa[x],z=fa[y];
        if(z!=to)
        {
            bool kx=idenify(x),ky=idenify(y);
            if(kx==ky)rotate(y);
            else rotate(x);
        }
        rotate(x);
    }
    if(!to)rt=x;
}
int kth(int k)
{
    int cur=rt;
    while(true)
    {
        pushdown(cur);
        if(ch[cur][0] && k<=siz[ch[cur][0]])cur=ch[cur][0];
        else if(k>cnt[cur]+siz[ch[cur][0]])
        {
            k-=cnt[cur]+siz[ch[cur][0]];
            cur=ch[cur][1];
        }
        else 
        {
            splay(cur);
            return cur;
        }
    }
}
void insert(int x)
{
    int cur=rt,p=0;
    while(cur && val[cur]!=x)
    {
        p=cur;
        cur=ch[cur][x>val[cur]];
    }
    if(cur)cnt[cur]++;
    else
    {
        cur=++num;
        ch[cur][0]=ch[cur][1]=0;
        val[cur]=x;
        siz[cur]=cnt[cur]=1;
        connect(cur,p,x>val[p]);
    }
    splay(cur);
}
void reverse(int l,int r)
{
    int x=kth(l),y=kth(r+2);
    splay(x);
    splay(y,x);
    rev[ch[y][0]]=!rev[ch[y][0]];
}
void print(int x)
{
    if(!x)return;
    pushdown(x);
    print(ch[x][0]);
    if(val[x]>=1 && val[x]<=n)cout<<val[x]<<' ';
    print(ch[x][1]);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n+1;i++)connect(i,i+1,0);
    for(int i=1;i<=n+2;i++)
    {
        cnt[i]=1;
        siz[i]=i;
    }
    val[1]=INT_MIN;
    val[n+2]=INT_MAX;
    for(int i=2;i<=n+1;i++)val[i]=i-1;
    rt=n+2;
    num=n+2;
    while(m--)
    {
        int l,r;
        cin>>l>>r;
        reverse(l,r);
    }
    print(rt);
    return 0;
}

by Kubic @ 2020-03-01 17:06:16

@limaopipi2022 您难道不觉得麻烦？

by Prean @ 2020-03-01 17:07:51

@Kubic 我习惯压行的。。。。。。

by Prean @ 2020-03-01 17:10:36

@Alpha 这是我从模板题的AC代码复制过来的，前面的 Zig 、 Zag 函数都没改过，因为要旋转到右儿子的关系改了一下 Splay ，但是问题应该不在这儿吧？

另：我会再对照你的代码看看哪儿错了

by Prean @ 2020-03-01 17:13:57

@limaopipi2022 对了。。。。。。想起来后面压行的时候把 Ln 、 Rn 和 num 删了

by Prean @ 2020-08-30 11:11:13

回头看了看自己的sb平衡树，发现旋转的时候都没有下传lazytag/xk