刚学Splay,求助

optimize_2 @ 2020-07-27 17:02:55

#include<iostream>
using namespace std;

struct SplayNode {
    int fa;
    int val;
    int size;
    int son[2];

    bool tag;

    #define fa(x) t[x].fa
    #define val(x) t[x].val
    #define size(x) t[x].size
    #define tag(x) t[x].tag
    #define ls(x) t[x].son[0]
    #define rs(x) t[x].son[1]
}t[10010];
int rt,tot;

int n,m,a[100010];
int x,y;

int whichSon(int x) {return x==rs(fa(x));}

void update(int x) {
    if(!x) return;
    size(x)=1;
    if(ls(x)) size(x)+=size(ls(x));
    if(rs(x)) size(x)+=size(rs(x));
}

void push_down(int x) {
    if(x&&tag(x)) {
        tag(ls(x))^=1;
        tag(rs(x))^=1;
        swap(ls(x),rs(x));
        tag(x)=0;
    }
}

void rotate(int x) {
    int s=whichSon(x);
    int of=fa(x);
    int s2=whichSon(of);
    int gf=fa(of);
    push_down(of);
    push_down(gf);
    if(t[x].son[s^1]) {
        t[of].son[s]=t[x].son[s^1];
        fa(t[x].son[s^1])=of;
    }
    fa(of)=x;
    fa(x)=gf;
    t[x].son[s^1]=of;
    if(gf) t[gf].son[s2]=x;
}

void splay(int x,int goal) {
    for(int f;(f=fa(x))!=goal;rotate(x))
        if(fa(f)!=goal)
            if(whichSon(x)==whichSon(f)) rotate(f);
            else rotate(x);
    if(goal==0) rt=x;
}

int findKth(int x) {
    int now=rt;
    while(1) {
        push_down(now);
        if(size(ls(x))>=x) now=ls(x);
        else {
            x-=size(ls(x))+1;
            if(x==0) return now;
            else now=rs(x);
        }
    }
}

void reverse(int x,int y) {
    int l=findKth(x-1),r=findKth(y+1);
    splay(l,0);
    splay(r,l);
    int pos=ls(rs(rt));
    tag(pos)^=1;
}

void print(int now) {
    //cout<<now<<" "<<ls(now)<<" "<<rs(now)<<endl;
    push_down(now);
    if(ls(now)) print(ls(now));
    if(val(now)!=-2147483647&&val(now)!=2147483647){
        cout<<val(now)<<" ";
    }
    if(rs(now)) print(rs(now));
}

int build(int l,int r,int f) {
    if(l>r) return 0;
    int mid=(l+r)>>1;
    tot++;
    fa(tot)=f;
    ls(tot)=0;
    rs(tot)=0;
    val(tot)=a[mid];
    size(tot)=1;
    ls(tot)=build(l,mid-1,tot);
    rs(tot)=build(mid+1,r,tot);
    update(tot);
    return tot;
}

int main() {
    cin>>n>>m;
    a[1]=-2147483647;
    a[n+2]=2147483647;
    for(int i=2;i<=n+1;i++) {
        a[i]=i-1;
    }

    rt=build(1,n+2,0);
    //reverse(2,5);

    for(int i=1;i<=m;i++) {
        cin>>x>>y;
        reverse(x+1,y+1);//在这挂了
        print(rt);
    }
    print(rt);

}

by t162 @ 2020-07-27 17:12:25

这注释打了和没打有什么区别

by kevin_max @ 2020-07-27 17:28:26

怀疑你是想来装b的

by optimize_2 @ 2020-07-27 17:43:28

@kevin_max bys,jbl

by optimize_2 @ 2020-07-27 17:44:30

找到一个问题

新事发现场见注释

#include<bits/stdc++.h>
using namespace std;

struct SplayNode {
    int fa;
    int val;
    int size;
    int son[2];

    bool tag;

    #define fa(x) t[x].fa
    #define val(x) t[x].val
    #define size(x) t[x].size
    #define tag(x) t[x].tag
    #define ls(x) t[x].son[0]
    #define rs(x) t[x].son[1]
}t[10010];
int rt,tot;

int n,m,a[100010];
int x,y;

int whichSon(int x) {return x==rs(fa(x));}

void update(int x) {
    if(!x) return;
    size(x)=1;
    if(ls(x)) size(x)+=size(ls(x));
    if(rs(x)) size(x)+=size(rs(x));
}

void push_down(int x) {
    if(x&&tag(x)) {
        tag(ls(x))^=1;
        tag(rs(x))^=1;
        swap(ls(x),rs(x));
        tag(x)=0;
    }
}

void rotate(int x) {
    int s=whichSon(x);
    int of=fa(x);
    int s2=whichSon(of);
    int gf=fa(of);
    push_down(of);
    push_down(gf);
    if(t[x].son[s^1]) {
        t[of].son[s]=t[x].son[s^1];
        fa(t[x].son[s^1])=of;
    }
    fa(of)=x;
    fa(x)=gf;
    t[x].son[s^1]=of;
    if(gf) t[gf].son[s2]=x;
}

void splay(int x,int goal) {
    for(int f;(f=fa(x))!=goal;rotate(x))
        if(fa(f)!=goal) {
            /*
            if(whichSon(x)==whichSon(f)) rotate(f);
            else rotate(x);
            */
            rotate(whichSon(x)==whichSon(f)?f:x);//here
        }

    if(goal==0) rt=x;
}

int findKth(int x) {
    int now=rt;
    while(1) {
        //cout<<x<<" "<<size(ls(x))<<" "<<size(rs(x))<<endl;
        push_down(now);
        if(size(ls(now))>=x) now=ls(x);
        else {
            x-=size(ls(now))+1;
            if(x==0) return now;
            else now=rs(x);
        }
    }
}

void reverse(int x,int y) {
    int l=findKth(x-1),r=findKth(y+1);
    //cout<<"ww";
    splay(l,0);
    splay(r,l);
    int pos=ls(rs(rt));
    tag(pos)^=1;
}

void print(int now) {
    //cout<<now<<" "<<ls(now)<<" "<<rs(now)<<endl;
    push_down(now);
    if(ls(now)) print(ls(now));
    if(val(now)!=-2147483647&&val(now)!=2147483647){
        cout<<val(now)<<" ";
    }
    if(rs(now)) print(rs(now));
}

int build(int l,int r,int f) {
    if(l>r) return 0;
    int mid=(l+r)>>1;
    tot++;
    fa(tot)=f;
    ls(tot)=0;
    rs(tot)=0;
    val(tot)=a[mid];
    size(tot)=1;
    ls(tot)=build(l,mid-1,tot);
    rs(tot)=build(mid+1,r,tot);
    update(tot);
    return tot;
}

int main() {
    cin>>n>>m;
    a[1]=-2147483647;
    a[n+2]=2147483647;
    for(int i=2;i<=n+1;i++) {
        a[i]=i-1;
    }

    rt=build(1,n+2,0);
    //reverse(2,5);

    for(int i=1;i<=m;i++) {
        cin>>x>>y;
        reverse(x+1,y+1);
        print(rt);
    }
    print(rt);

}

by kevin_max @ 2020-07-27 17:48:21

@optmize_2 bys，jbl

by Aw顿顿 @ 2020-07-27 21:49:17

@kevin_max 人家做题做错了发个贴求助你在下面水，然后还说人家 bys？

by JRzyh @ 2020-07-27 21:53:01

在学术帖狂氵被D还理直气壮反D，理由：别人也这样啊

by Chancylaser @ 2020-07-28 07:34:35

@optmize_2 啊，真萌啊，真是%*&……（