萌新求助

RT，完全死掉

#include <iostream>
#include <cstdio>
#include <algorithm>
#define yycoi 3
const int N=100000;
const int M=100000;
int n, m;
int rt;
int a[N+10];
struct node
{
    int val;
    int cnt;
    int fa;
    int son[2];
    int siz;
    bool tag;
} spl[N+10];
int cnt_node;
inline int chk(int i)
{
    return spl[spl[i].fa].son[1]==i;
}
inline void push_up(int i)
{
    spl[i].siz=spl[spl[i].son[0]].siz+spl[spl[i].son[1]].siz
        +spl[i].cnt;
    return;
}
inline void push_down(int i)
{
    if (spl[i].tag)
        std::swap(spl[i].son[0], spl[i].son[1]);
    spl[spl[i].son[0]].tag^=spl[i].tag;
    spl[spl[i].son[1]].tag^=spl[i].tag;
    spl[i].tag=0;
    return;
}
inline void spin(int i)
/// Unlike spin in treap, this function make point i less deeper
{
    int dir=chk(i);
    int ison=spl[i].son[dir^1];
    int ifa=spl[i].fa;
    int igrandfa=spl[ifa].fa;
    spl[i].son[dir^1]=ifa;
    spl[ifa].fa=i;
    spl[igrandfa].son[chk(ifa)]=i;
    spl[i].fa=igrandfa;
    spl[ifa].son[dir]=ison;
    spl[ison].fa=ifa;
    return;
}
void splay(int i, int targ=0)
{
    #if yycoi==2
    printf("in splay %d for %d\n", i, targ);
    #endif // yycoi
    while (spl[i].fa!=targ)
    {
        int ifa=spl[i].fa, igrandfa=spl[ifa].fa;
        if (igrandfa!=targ)
        {
            if (chk(i)==chk(ifa))
                spin(ifa);
            else
                spin(i);
        }
        spin(i);
    }
    if (targ==0)
        rt=i;
    return;
}
void build(int i, int l, int r)
{
    int mid=(l+r)>>1;
    spl[i].cnt=1;
    spl[i].siz=1;
    spl[i].tag=0;
    spl[i].val=a[mid];
    if (l==r)
        return;
    if (l<=mid-1)
    {
        spl[i].son[0]=++cnt_node;
        spl[cnt_node].fa=i;
        build(spl[i].son[0], l, mid-1);
    }
    if (mid+1<=r)
    {
        spl[i].son[1]=++cnt_node;
        spl[cnt_node].fa=i;
        build(spl[i].son[1], mid+1, r);
    }
    push_up(i);
    return;
}
int getkth(int i, int k)
{
    #if yycoi==2
    printf("in %d-th in node %d value %d\n", k, i, spl[i].val);
    //system("pause");
    #endif // yycoi
    push_down(i);
    if (k>spl[spl[i].son[0]].siz+spl[i].cnt)
        return getkth(spl[i].son[1], k-spl[spl[i].son[0]].siz-spl[i].cnt);
    else if (k<=spl[spl[i].son[0]].siz)
        return getkth(spl[i].son[0], k);
    else
        return i;
}
void rev(int l, int r)
{
    #if yycoi==2
    printf("in rev from %d to %d\n", l, r);
    #endif // yycoi
    splay(getkth(rt, l));
    splay(getkth(rt, r+2), rt);
    spl[spl[spl[rt].son[1]].son[0]].tag^=1;
    return;
}
void out(int i=rt)
{
    #if yycoi>=2
    printf("in out %d\n", i);
    #endif // yycoi
    push_down(i);
    if (spl[i].son[0])
        out(spl[i].son[0]);
    if (spl[i].val>=1&&spl[i].val<=n)
        printf("%d ", spl[i].val);
    if (spl[i].son[1])
        out(spl[i].son[1]);
    return;
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i=0; i<=n+1; ++i)
        a[i]=i;
    rt=++cnt_node;
    build(rt, 0, n+1);
    #if yycoi==2
    out();
    putchar('\n');
    #endif // yycoi
    for (int i=1; i<=m; ++i)
    {
        int l, r;
        scanf("%d%d", &l, &r);
        rev(l, r);
        #if yycoi<=3&&yycoi>=2
        out();
        putchar('\n');
        #endif // yycoi
    }
    out();
    putchar('\n');
    return 0;
}