Splay 区间反转

同样的，我们以一道题来引入。

这次的任务比较少，只要求进行区间反转。区间反转？

这个好像用啥都是O（n）的吧……（这次vector，set也救不了你了）

我们来使用splay解决这个问题。我们既然要反转一段区间，那我们肯定要把这个区间弄到一个地方。我们想一下上次所讲的删除操作，我们把要删除的数的前驱后继都找了出来并且一个旋转到根，一个到根的右儿子。我们思考一下发现，如果把这个区间第一个数的前一个数（l-1）旋转到根，把区间最后一个数的后一个数（r+1）旋转到根的右儿子，那么现在根的右儿子的左子树就是这个区间了！

然后我们就可以大力（划死）操作这棵子树，比如进行区间加减，区间翻转。翻转其实很简单，我们只要打上一个标记，在下放标记的时候，我们把当前节点的左右子树交换，把左右子树的标记全部异或1，把这个点的标记清零即可。（和线段树下放lazy标记非常像）

然后实际操作的时候，比如我们要翻转区间2～4，我们不是真的去找这俩数在哪，因为我们要反转的话其实和数的大小是无关的，和下标的大小是有关的。取而代之的，我们找到在这棵平衡树中相对应的排名为2和排名为4的两个数的编号是多少，之后我们对它们进行操作即可。

然后最后我们在输出整棵树的时候只要输出其中序遍历即可。

我们来看一下代码吧！

#include<iostream>

#include<cstdio>

#include<cmath>

#include<algorithm>

#include<queue>

#include<cstring>

#define rep(i,a,n) for(int i = a;i <= n;i++)

#define per(i,n,a) for(int i = n;i >= a;i--)

#define enter putchar('\n')

#define pr pair<int,int>

#define mp make_pair

#define fi first

#define sc second

using namespace std;

typedef long long ll;

const int M = ;

const int N = ;

const int INF = ;

int read()

{

    int ans = ,op = ;

    char ch = getchar();

    while(ch < '' || ch > '')

    {

    if(ch == '-') op = -;

    ch = getchar();

    }

    while(ch >='' && ch <= '')

    {

    ans *= ;

    ans += ch - '';

    ch = getchar();

    }

    return ans * op;

}

struct node

{

    int fa,ch[],son,cnt,tag,val;

}t[M<<];

int n,m,data[M<<],root,x,y,idx;

bool get(int x)

{

    return t[t[x].fa].ch[] == x;

}

void pushup(int x)

{

    t[x].son = t[t[x].ch[]].son + t[t[x].ch[]].son + ;//题中无重复的数

}

void pushdown(int x)

{

    if(x && t[x].tag)

    {

    t[t[x].ch[]].tag ^= ,t[t[x].ch[]].tag ^= ;

    swap(t[x].ch[],t[x].ch[]);

    t[x].tag = ;

    }

}

void rotate(int x)

{

    int y = t[x].fa,z = t[y].fa,k = get(x);

    t[z].ch[t[z].ch[] == y] = x,t[x].fa = z;

    t[y].ch[k] = t[x].ch[k^],t[t[y].ch[k]].fa = y;

    t[x].ch[k^] = y,t[y].fa = x;

    pushup(x),pushup(y);

}

void splay(int x,int goal)

{

    while(t[x].fa != goal)

    {

    int y = t[x].fa,z = t[y].fa;

    if(z != goal) (t[y].ch[] == x) ^ (t[z].ch[] == y) ? rotate(x) : rotate(y);

    rotate(x);

    }

    if(goal == ) root = x;

}

int rk(int x)//找排名

{

    int u = root;

    while()

    {

    pushdown(u);

    if(t[t[u].ch[]].son >= x) u = t[u].ch[];

    else

    {

        x -= (t[t[u].ch[]].son + );

        if(!x) return u;

        u = t[u].ch[];

    }

    }

}

int build(int f,int l,int r)//直接构造一棵完美的splay

{

    if(l > r) return ;

    int mid = (l+r) >> ,u = ++idx;

    t[u].val = data[mid],t[u].fa = f;//注意一定是mid的值！

    t[u].ch[] = build(u,l,mid-);

    t[u].ch[] = build(u,mid+,r);

    pushup(u);

    return u;

}

void turn(int x,int y)

{

    int a = rk(x), b = rk(y+);//因为插入了正负INF，所以相对应都向后移了一位

    splay(a,),splay(b,a);//以下操作上面都说过

    pushdown(root);

    int g = t[t[root].ch[]].ch[];

    t[g].tag ^= ;

}

void write(int x)//输出中序遍历

{

    pushdown(x);

    if(t[x].ch[]) write(t[x].ch[]);

    if(t[x].val != INF && t[x].val != -INF) printf("%d ",t[x].val);

    if(t[t[x].ch[]].val) write(t[x].ch[]);

}

int main()

{

    n = read(),m = read();

    rep(i,,n) data[i+] = i;

    data[] = -INF,data[n+] = INF;//防止出错

    root = build(,,n+);

    rep(i,,m) x = read(),y = read(),turn(x,y);

    write(root);

    return ;

}

巴特西

Splay 区间反转

最新文章

热门文章