求助。。。本机RE

P3391 【模板】文艺平衡树

xiaolou @ 2019-03-28 19:31:34

RT,好像Kth挂了。。。

#include <bits/stdc++.h>

using namespace std;
struct Node
{
    int sz,v,f;
    Node *s[2],*fa;
}pool[100005],*root;
int Size(Node *p)
{
    if(!p)
    {
        return 0; 
    }
    return p->sz;
}
void Pushdown(Node *p)
{
    if(p->f)
    {
        if(p->s[0])
        {
            p->s[0]->f=1;
        }
        if(p->s[1])
        {
            p->s[1]->f=1;
        }
    }
    p->f=0;
}
void Update(Node *p)
{
    p->sz=Size(p->s[0])+Size(p->s[1])+1;
    if(p->s[0])
    {
        Pushdown(p->s[0]);
    }
    if(p->s[1])
    {
        Pushdown(p->s[1]);
    }
}
void Rotate(Node *p)
{
    int k=0;
    if(p->fa->s[1]==p)
    {
        k=1;
    }
    Node *fa=p->fa;
    Node *gf=p->fa->fa;
    Node *son=p->s[!k];
    fa->s[k]=son;
    if(son)
    {
        son->fa=fa;
    }
    fa->fa=p;
    p->s[!k]=fa;
    p->fa=gf;
    if(gf)
    {
        if(gf->s[1]==fa)
        {
            gf->s[1]=p;
        }
        else
        {
            gf->s[0]=p;
        }
    }
    if(root==fa)
    {
        root=p;
    }
    Update(fa);
    Update(p);
}
Node *Kth(Node *p,int x)
{
    if(Size(p->s[0])+1==x) 
    {
        return p;
    }
    else if(Size(p->s[0])+1>x)
    {
        return Kth(p->s[0],x);
    }
    else
    {
        return Kth(p->s[1],x-(Size(p->s[0])+1));
    }
}
void Splay(Node *p,Node *tar)
{
    while(p->fa!=tar)
    {
        if(p->fa->fa==tar)
        {
            Rotate(p);
        }
        else
        {
            Node *fa=p->fa;
            Node *gp=p->fa->fa;
            int k=(gp->s[1]==fa);
            if(p==fa->s[k]) 
            {
                Rotate(fa); 
                Rotate(p);
            }
            else
            {
                Rotate(p); 
                Rotate(p);
            }
        }
    }
}     
int cnt=0;
void Reverse(int x,int y)
{
    Node *l=Kth(root,x-1);
    Node *r=Kth(root,y+1);
    printf("1\n");
    Splay(l,NULL);
    Splay(r,root);
    if(root->s[1]->s[0])
    {
        root->s[1]->s[0]->f=1;
    }
}
void Inorder(Node *p)
{
    if(p->s[0])
    {
        Inorder(p->s[0]);
    }
    printf("%d ",p->v);
    if(p->s[1])
    {
        Inorder(p->s[1]);
    }
}
void Insert(int x)
{
    Node *p=&pool[++cnt];
    Node *p1=Kth(root,x-1);
    Splay(p1,NULL);
    root->s[1]=p;
    p->v=x;
    p->sz=1;
    p->fa=root;
    Update(p);
    Update(root);
}

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    root=&pool[++cnt];
    root->v=1;
    root->sz=1;
    for(int i=2;i<=n+2;++i)
    {
        Insert(i);
    }
    for(int i=1;i<=m;++i)
    {
        int a,b;
        cin >> a >> b;
        Reverse(a,b);
    }
    Inorder(root);
    return 0;
}

by TLE自动机 @ 2019-04-10 13:59:08

表示看不懂指针QAQ

但是我一开始也是kth有锅,自己调了下发现要返回节点编号。。(逃


|