关于splay中“哨兵”的问题

P3391 【模板】文艺平衡树

狛枝凪斗 @ 2019-06-16 11:57:26

众所周知哨兵就是splay中一大一小两个安全保险XD 今天写这道板子题的时候怎么样都没法输出,后来调整了一下哨兵的插入顺序就过了,但理解上觉得插入顺序应该没有影响,同机房的大佬也说应该没有影响,并且他的代码改了插入顺序以后依然没有问题 我能过的代码:

#include<iostream>
#include<cstdio>
using namespace std;
const int INF=2147483647;
int n,m,tot,root;
struct node{
    int ch[2],siz,cnt,val,fa,tag;
}a[210010];
void pushdown(int x){
    if(a[x].tag){
        a[a[x].ch[0]].tag^=1;
        a[a[x].ch[1]].tag^=1;
        a[x].tag=0;
        swap(a[x].ch[0],a[x].ch[1]);
    }
}
void update(int x){
    a[x].siz=a[a[x].ch[0]].siz+a[a[x].ch[1]].siz+a[x].cnt;
}
void rotate(int x){
    int y=a[x].fa,z=a[y].fa;
    int k=(a[y].ch[1]==x);
    a[z].ch[a[z].ch[1]==y]=x;
    a[x].fa=z;
    a[y].ch[k]=a[x].ch[k^1];
    a[a[x].ch[k^1]].fa=y;
    a[x].ch[k^1]=y;
    a[y].fa=x;
    update(y),update(x);
}
void splay(int x,int goal){
    while(a[x].fa!=goal){
        int y=a[x].fa,z=a[y].fa;
        if(z!=goal){
            (a[z].ch[0]==y)^(a[y].ch[0]==x)?rotate(x):rotate(y);
        }
        rotate(x);
    }
    if(goal==0)root=x;
}
void insert(int x){
    int u=root,ff=0;
    if(u&&a[u].val!=x){
        ff=u;
        u=a[u].ch[x>a[u].val];
    }
    if(u)a[u].cnt++;
    else{
        u=++tot;
        if(ff)a[ff].ch[x>a[ff].val]=u;
        a[tot].fa=ff,a[tot].val=x;
        a[tot].cnt=a[tot].siz=1;
        a[tot].ch[0]=a[tot].ch[1]=0;
    }
    splay(u,0);
}
int findval(int x){
    int u=root;
    while(1){
        pushdown(u);
        int v=a[u].ch[0];
        if(x>a[v].siz+a[u].cnt){
            x-=a[v].siz+a[u].cnt;
            u=a[u].ch[1];
        }
        else if(a[v].siz>=x)u=v;
        else return u;
    }
}
void work(int l,int r){
    int last=findval(l-1);
    int nex=findval(r+1);
    splay(last,0),splay(nex,last);
    a[a[a[root].ch[1]].ch[0]].tag^=1;
}
void pri(int u){
    pushdown(u);
    if(a[u].ch[0])pri(a[u].ch[0]);//if(a[u].val!=INF&&a[u].val!=-INF)
    printf("%d ",a[u].val);
    if(a[u].ch[1])pri(a[u].ch[1]);
}
int main()
{
    scanf("%d%d",&n,&m);
    insert(-INF);
    for(int i=1;i<=n;i++)insert(i);
    insert(INF);
    while(m--){
        int l,r;
        scanf("%d%d",&l,&r);
        work(l+1,r+1);
    }
    pri(root);
    return 0;
}

这个是调整插入顺序后的,只修改了这一部分:

    ...
    scanf("%d%d",&n,&m);
    insert(-INF),insert(INF);
    for(int i=1;i<=n;i++)insert(i);
   while(m--)
   ...

大佬说应该是平衡树本身写错了,但我不太明白…刚学平衡树,想请教一下诸位大佬们这是怎么回事?


by 狛枝凪斗 @ 2019-06-16 11:57:59

其实不是哨兵的问题?


by charliegong @ 2019-06-16 12:01:47

太难了,下一个


by zl_just @ 2019-06-16 12:03:23

@狛枝凪斗 其实哨兵只要一个就好了,但pri中的if语句为什么删了?


by syksykCCC @ 2019-06-16 12:08:56

@狛枝凪斗 我就是像你原来那样插入的呀,没有问题啊,你可以看我的代码


by Dasknight @ 2019-06-16 13:17:26

哨兵还有问题。。。


by 狛枝凪斗 @ 2019-06-16 14:03:41

@zl_just 调试的时候删了然后忘记改回来 问题不在这里XD


by 狛枝凪斗 @ 2019-06-16 14:04:22

@syksykCCC 调整插入顺序后的错了


by 晚安晚安 @ 2019-06-18 15:43:52

哨兵表示它兢兢业业的不背这个锅


|