样例都过不去,求助

P3391 【模板】文艺平衡树

liuyifan @ 2019-02-19 10:32:37

RT.样例输出1 2 3 4 5

#include<bits/stdc++.h>
#define reg register
#define ll long long
#define find liuyifan_find
#define inf 0x3f3f3f3f
using namespace std;
class node
{
    public:
        int ch[2],fa,v,size;
        bool bj;
        inline void set(int x)
        {
            v=x;
            ch[0]=ch[1]=fa=bj=0;
            size=1;
        }
}tree[100005];
int n,m,root,tot,l,r,x1,x2;
inline int read()
{
    reg int x=0,w=0;
    reg char ch=0;
    while(!isdigit(ch))
    {
        w|=ch=='-';
        ch=getchar();
    }
    while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return w?-x:x;
}
inline void update(reg int x)
{
    if(!x)return;
    tree[x].size=1+tree[tree[x].ch[0]].size+tree[tree[x].ch[1]].size;
}
inline bool son(reg int x)
{
    return tree[tree[x].fa].ch[1]==x;
}
inline int build(reg int l,reg int r)
{
    if(l>r)return 0;
    reg int x=++tot,mid=(l+r)>>1;
    tree[x].set(mid);
    tree[x].ch[0]=build(l, mid-1);
    tree[x].ch[1]=build(mid+1, r);
    tree[tree[x].ch[0]].fa=tree[tree[x].ch[1]].fa = x;
    update(x);
    return x;
}
inline void pushdown(reg int x)
{
    if(!x)return;
    if(tree[x].bj)
    {
        tree[tree[x].ch[0]].bj^=1;
        tree[tree[x].ch[1]].bj^=1;
        tree[x].bj=0;
        tree[x].ch[0]=tree[x].ch[1];
        tree[x].ch[1]=tree[x].ch[0];
    }
}
inline void link(reg int x,reg int y,reg bool cc)
{
    tree[x].ch[cc]=y;
    tree[y].fa=x;
}
inline void rotate(reg int x)
{
    reg int fa=tree[x].fa,fafa=tree[fa].fa,tt=son(x);
    link(fafa,x,son(fa));
    link(fa,tree[x].ch[!tt],tt);
    link(x,fa,!tt);
    update(fa);
}
inline void splay(reg int x,reg int f)
{
    pushdown(x);
    if(!f)root=x;
    while(tree[x].fa!=f)
    {
        if(tree[tree[x].fa].fa==f)
        {
            rotate(x);
            break;
        }
        if(son(x)==son(tree[x].fa))
        {
            rotate(tree[x].fa);
            rotate(x);
        }
        else
        {
            rotate(x);
            rotate(x);
        }
    }
    update(x);
}
inline int find(reg int x,reg int y)
{
    pushdown(x);
    if(tree[tree[x].ch[0]].size+1<y)return find(tree[x].ch[1],y-tree[tree[x].ch[0]].size-1);
    else if(tree[tree[x].ch[0]].size+1==y)return x;
    else return find(tree[x].ch[0],y);
}
inline void dfs(reg int x)
{
    pushdown(x);
    if(tree[x].ch[0])dfs(tree[x].ch[0]);
    if(tree[x].v<=n&&tree[x].v>=1)printf("%d ",tree[x].v);
    if(tree[x].ch[1])dfs(tree[x].ch[1]);
}
int main()
{
    n=read(),m=read();
    tree[0].v=tree[n+1].v=inf;
    root=build(0,n+1);
    for(reg int i=1;i<+m;i++)
    {
        l=read(),r=read();
        x1=find(root,l);
        x2=find(root,r+2);
        splay(x1,0);
        splay(x2,x1);
        update(root);
        tree[tree[x2].ch[0]].bj^=1;
        update(tree[x2].ch[0]);
        update(x2);
        update(root);
    }
    dfs(root);
    return 0;
}

by wubaiting2020 @ 2019-02-19 10:34:42

splay


by liuyifan @ 2019-02-19 11:05:18

splay


|