数据过水，Splay只单旋不双旋过了

从蒟蒻到小犇 @ 2024-07-02 20:55:04

by 从蒟蒻到小犇 @ 2024-07-02 21:11:04

#include<bits/stdc++.h>
using namespace std;
const int mn=1e5;
#define 左子 t[o].son[0]
#define 右子 t[o].son[1]
#define ls son[0]
#define rs son[1]
#define 真根 t[root].ls

int n,m,root;
struct Tree{
    int 父亲,son[2];
    int siz;
    int lazy翻转;
}t[mn+5];
inline bool whichson(int o) {//左子还是右子
    return t[t[o].父亲].son[0]==o?0:1;
}
inline void Up(int o) {
    t[o].siz=t[左子].siz+1+t[右子].siz;
}
inline void Down(int o) {
    if(t[o].lazy翻转) {
        swap(左子,右子);
        t[左子].lazy翻转^=1;
        t[右子].lazy翻转^=1;
        t[o].lazy翻转=false;
    }
}
int Build(int l,int r) {
    if(l>r) return 0;

    int o=(l+r)>>1;
    t[o].父亲=t[o].siz=t[o].lazy翻转=0;
    左子=Build(l,o-1);
    右子=Build(o+1,r);
    t[左子].父亲=t[右子].父亲=o;
    Up(o);
    return o;
}
void See(int o) {
    if(o==0) return;
    Down(o);
    See(左子);
    if(1<=o-1&&o-1<=n) printf("%d ",o-1);
    See(右子);
}

void Lrotate(int y) {
    //重点：按顺序改三个点的父亲、三个点的儿子！！！
    int x=t[y].父亲;
    t[t[x].父亲].son[whichson(x)]=y;

    t[x].rs=t[y].ls;
    t[y].ls=x;
    t[t[x].rs].父亲=x;
    t[y].父亲=t[x].父亲;
    t[x].父亲=y;
    Up(x);Up(y);
}
void Rrotate(int y) {
    //重点：按顺序改三个点的父亲、三个点的儿子！！！
    int x=t[y].父亲;
    t[t[x].父亲].son[whichson(x)]=y;

    t[x].ls=t[y].rs;
    t[y].rs=x;
    t[t[x].ls].父亲=x;
    t[y].父亲=t[x].父亲;
    t[x].父亲=y;
    Up(x);Up(y);
}
void rotate(int o) {
    (whichson(o)==0)?Rrotate(o):Lrotate(o);
}
int Find(int o,int k) {
    //找排名为k的点，重点：注意先Down!!!
    Down(o);
    if(k==t[左子].siz+1) return o;
    else if(k<=t[左子].siz) return Find(左子,k);
    else return Find(右子,k-t[左子].siz-1);
}
void Splay(int o,int target) {
    //向上转直到o的父亲为target
    while(t[o].父亲!=target) {
        rotate(o);
    }
}

int main() {
    cin>>n>>m;
    root=n+3;//设置一个虚拟点root
    t[root].ls=Build(1,n+2);
    t[root].siz=n+3;
    t[(1+n+2)>>1].父亲=root;

    for(int z=1;z<=m;z++) {
        int l,r;
        scanf("%d%d",&l,&r);
        ++l;++r;

        Splay(Find(真根,l-1),root);
        Splay(Find(t[真根].rs,(r+1)-(l-1)),真根);
        //把两个点转到最上面
        t[t[t[真根].rs].ls].lazy翻转^=1;
    }
    See(真根);
    return 0;
}

by jy20091121 @ 2024-07-12 20:55:17

你这代码6