信LRJ得永生

这样是错的：

···

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define For(i , j , k) for (int i = (int)(j) ; i <= (int)(k) ; ++ i)
#define Fordown(i , j , k) for (int i = (int)(j) ; i >= (int)(k) ; -- i)
#define Set(a , b) memset(a , b , sizeof(a))
using namespace std;
const int maxn = 100010;
struct node
{
    node *ch[2];
    int num , s , flag;
    node()
    {
        s = flag = num = 0;
    }
}*rt , *null;
int n , m , nn , l , r , ans[maxn] , anss;
inline int cmp(node *o , int k)
{
    int d = k - o->ch[0]->s;
    if (d == 1)
        return -1;
    return d <= 0 ? 0 : 1;
}
inline void maintain(node* &o)
{
    o -> s = 1 + o -> ch[0] -> s + o -> ch[1] -> s;
}
inline void pushdown(node* &o)
{
    if (o -> flag)
    {
        o -> flag = 0;
        swap(o -> ch[0] , o -> ch[1]);
        o -> ch[0] -> flag ^= 1;
        o -> ch[1] -> flag ^= 1;
    }
}
node* build(int k)
{
    if (!k)
        return null;
    node *o = new node;
    o -> ch[0] = build(k / 2);
    o -> num = ++ n;
    o -> ch[1] = build(k - k / 2 - 1);
    o -> flag = o -> s = 0;
    maintain(o);
    return o;
}
void Init()
{
    scanf("%d%d" , &nn , &m);
    null = new node;
    n = 0;
    rt = build(nn + 1);
}
void rotate(node* &o , int d)
{
    node *k;
    k = o -> ch[d ^ 1];
    o -> ch[d ^ 1] = k -> ch[d];
    k -> ch[d] = o;
    maintain(o);
    maintain(k);
    o = k;
}
void splay(node* &o , int k)
{
    pushdown(o);
    int d = cmp(o , k);
    if (d == 1)
        k -= o->ch[0]->s + 1;
    if (d >= 0)
    {
        node *p = o -> ch[d];
        pushdown(p);
        int d2 = cmp(p , k);
        int k2 = k;
        if (d2)
            k2 -= p->ch[0]->s + 1;
        if (d2 != -1)
        {
            splay(p->ch[d2] , k2);
            if (d == d2)
                rotate(o , d ^ 1);
            else
                rotate(p , d);
        }
        rotate(o , d ^ 1);
    }
}
node* merge(node* l , node* r)
{
    splay(l , l -> s);
    l -> ch[1] = r;
    maintain(l);
    return l;
}
void split(node* rt , int k , node* &l , node* &r)
{
    splay(rt , k);
    l = rt;
    r = rt -> ch[1];
    rt -> ch[1] = null;
    maintain(l);
}
void Solve()
{
    while (m --)
    {
        scanf("%d%d" , &l , &r);
        node *le , *ri , *mi , *o;
        split(rt , l , le , o);
        split(o , r - l + 1 , mi , ri);
        mi -> flag ^= 1;
        rt = merge(merge(le , mi) , ri);
    }
}
void Print(node *u)
{
    if (u == null)
        return ;
    pushdown(u);
    Print(u -> ch[0]);
    ans[anss ++] = u -> num;
    Print(u -> ch[1]);
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("Splay.in" , "r" , stdin);
    freopen("Splay.out" , "w" , stdout);
#endif
    Init();
    Solve();
    Print(rt);
    For(i , 1 , anss - 1)
        printf("%d " , ans[i] - 1);
    return 0;
}

··· 这样是对的：

有区别吗。。。

void rotate(node* &o , int d) { node *k; k = o -> ch[d ^ 1]; o -> ch[d ^ 1] = k -> ch[d]; k -> ch[d] = o; maintain(o); maintain(k); o = k; } void splay(node* &o , int k) { pushdown(o); int d = cmp(o , k); if (d == 1) k -= o->ch[0]->s + 1; if (d >= 0) { node *p = o -> ch[d]; pushdown(p); int d2 = cmp(p , k); int k2 = k; if (d2) k2 -= p->ch[0]->s + 1; if (d2 != -1) { splay(p->ch[d2] , k2); if (d == d2) rotate(o , d ^ 1); else rotate(o->ch[d] , d); } rotate(o , d ^ 1); } }