萌新求助splay,样例都过不去

P3391 【模板】文艺平衡树

lsy263 @ 2019-01-14 23:45:13

连样例都过不去

@ouuan

dalao您一定会qwq

root不知道为什么变成0,然后就死循环了

#include<iostream>
#define INF 0x7fffffff
using namespace std;
int root,tot;
const int SIZE=1e6;
struct TR{int tag,size,val,ch[2],f;}t[SIZE];
namespace SPLAY
{
    #define LS t[u].ch[0]
    #define RS t[u].ch[1]
    void pushdown(int u)
    {
        t[u].tag=0;
        t[LS].tag^=1,t[RS].tag^=1;
        //LS+=RS,RS=LS-RS,LS-=RS;
        swap(LS,RS);
    }
    inline void Link(int f, int son, int k) 
    {
        if(f) t[f].ch[k] = son;
        if(son) t[son].f = f;
    }
    void pushup(int u)
    {
        t[u].size=t[LS].size+t[RS].size+1;
    }
    void rotate(int x) 
    {
        int y=t[x].f;
        int z=t[y].f;
        int kx=t[y].ch[1]==x;
        int ky=t[z].ch[1]==y;
    //  Link(y,t[x].ch[kx],kx);
    //  Link(x,y,kx);
    //  Link(z,x,ky);
        //pushup(z);
        Link(y,t[x].ch[kx^1],kx);
        Link(x,y,kx^1); 
        Link(z,x,ky); 
        pushup(y);
        pushup(x);
    }
    void splay(int x,int to)
    {
        //
        while(t[x].f!=to)
        {
            int y=t[x].f;
            int z=t[y].f;
            //if(t[z].tag)pushdown(z);
            //if(t[y].tag)pushdown(y);
            //if(t[x].tag)pushdown(x);
            if(z!=to)rotate((t[y].ch[0]==x) ^ (t[z].ch[0]==y)?x:y);
            rotate(x);
        }
        if(!to) root=x;
    }
    void find(int x)
    {
        int u=root;
        if(!u)return;
        while(t[u].ch[ x>t[u].val ]&&x!=t[u].val)
        {
            if(t[u].tag)pushdown(u);
            u=t[u].ch[ x>t[u].val ];
        }
        splay(u,0);
    }
    void insert(int x)
    {
        int u=root,f=0;
        while(u)f=u,u=t[u].ch[ x>t[u].val ];
        u=++tot;
        if(f)t[f].ch[ x>t[f].val ]=u;
        t[u].f=f;
        t[u].val=x;
        t[u].size=1;
        LS=RS=t[u].tag=0;
        if(!root)root=u;
        splay(u,0);
    }
    int lower(int x)
    {
        find(x);
        if(t[root].val<x)return root;
        int u=root;
        u=LS;
        while(RS)u=RS;
        splay(u,0);
        return u;
    }
    int upper(int x)
    {
        find(x);
        if(t[root].val>x)return root;
        int u=root;
        u=RS;
        while(LS)u=LS;
        splay(u,0);
        return u;
    }
    int Kth(int k) //注意是改变第x大不是x号
    {
        int u=root;
        while(true)
        {
            if(t[u].tag)pushdown(u);
            if(k<=t[LS].size)u=LS;
            else
            {
                k-=t[LS].size+1;
                if(!k)return u;
                u=RS;
            }
        }

    }
    void change(int l,int r)
    {
        int x=Kth(l-1);
        int y=Kth(r+1);
        splay(x,0);
        splay(y,x);
        int u=root;u=RS;u=LS;
        t[u].tag^=1;
    }
    void midroot(int u)
    {
        if(t[u].tag)pushdown(u);
        if(LS)midroot(LS);
        if(t[u].val!=INF&&t[u].val!=-INF)
            cout<<t[u].val<<" ";
        if(RS)midroot(RS);
    }
}
using namespace SPLAY;
int main()
{
    freopen("data.in","r",stdin);
    int n,m;cin>>n>>m;
    t[0].size=0;
    insert(INF),insert(-INF);
    t[1].size=t[2].size=0;
    for(int i=1;i<=n;++i) 
        insert(i);
    int l,r;
    while(m--)
    {
        cin>>l>>r;
        change(l,r);
    }
    midroot(root);
    return 0;
}

by ouuan @ 2019-01-19 12:16:19

@lsy263 首先你要明白序列Splay中“大小”指的是在序列中位置的先后,而不是下标的大小。不知道你是不是这里理解有问题...


by lsy263 @ 2019-01-19 19:23:03

@ouuan 原来不是元素值的大小吗....qwq


上一页 |