天天看點
傳回

Splay bzoj3223文藝平衡樹

Splay，中文名伸展樹，是由tarjan大神發明的… orz

本質上就是BST加上splay操作——把結點x旋轉到指定結點的下面。

每次查詢完都把查到的數旋轉到根，就可以讓所有查找的時間效率為均攤O(logN) (不知道為啥…大佬說是就是吧orz)

因為Splay可以通過伸展操作随意改變樹的結構，隻要把排名L-1的結點伸展到根，把排名R+1的結點伸展到根的右孩子，R+1結點的左子樹就包含了區間[L,R]中所有的點，是以Splay做區間操作非常友善。

缺點大概就是大得驚人的常數吧。

Splay的定義:

int ch[maxn][2], fa[maxn], val[maxn], siz[maxn], lazy[maxn];
int tot,root;
#define ls ch[now][0]
#define rs ch[now][1]

跟Treap的定義基本一樣的，少個優先級，多個fa數組記錄該結點的父親。lazy是題目要用的翻轉标記。

宏是用來偷懶的~

為什麼Treap不要fa，Splay要？

因為Splay操作要用到父親的父親，不記錄fa不會寫。

旋轉rotate:

跟所有平衡樹的旋轉都是一樣的。get函數用來判斷該結點是它父親的哪個兒子。因為要維護區間，有些地方要pushup(把x旋轉到y的上面之後，y的子樹大小要重新計算)

貼張醜圖以供想象

Splay bzoj3223文藝平衡樹
bool get(int x)//傳回x是它父親的哪個兒子
{
    return x == ch[fa[x]][];
}

void connect(int son,int f,int dir)
{
    fa[son] = f;
    ch[f][dir] = son;
}

int y,z,yson,zson,xson;
void Rotate(int x)//把x旋轉到fa[x]的位置,用get來判斷要左旋還是右旋
{
    y = fa[x];
    z = fa[y];
    yson = get(x), zson = get(y);//記錄x和y是他們父親的哪個兒子
    xson = ch[x][yson^];
    connect(x,z,zson);
    connect(y,x,yson^);
    connect(xson,y,yson);
    pushup(y);
}

伸展splay——把x旋轉到to的下面，成為to的兒子

三種情況:

1.fa[fa[x]] == to

往上旋一次即可

2.get(x) == get(fa[x])

設y是x的父親，z是y的父親，這種情況下，xyz是共線的（自行腦補）

tarjan大佬說這種情況要先把y旋上去，再把x旋上去

3.其他情況

x往上旋兩次

void splay(int x,int to)//把x旋轉到to的下面
{
    pushdown(x);//旋轉後會改變結點關系，先下推标記！
    while(fa[x] != to)
    {
        if(fa[fa[x]] == to)
            Rotate(x);
        else if(get(x)==get(fa[x]))
            Rotate(fa[x]), Rotate(x);
        else
            Rotate(x), Rotate(x);
    }
    pushup(x);//旋轉後會子樹大小會變，更新
    if(to == )//x移到根了，更新根
        root = x;
}

建樹build:

跟線段樹差不多，多傳一個參數f用來維護fa數組

void build(int l,int r,int &now,int f)
{
    if(l>r) return ;
    int m = l + r >> ;
    newnode(m,now,f);
    build(l,m-,ls,now);
    build(m+,r,rs,now);
    pushup(now);
}

更新update(本題的更新是翻轉)

首先把 L-1 splay到root，把 R+1 splay到root下面

build前要插入兩個虛結點0和N+1，不然splay操作會越界

newnode(0,root,0);
    newnode(N+1,ch[root][1],root);
    build(1,N,ch[ch[root][1]][0],ch[root][1]);

但splay函數是把下标為x的結點旋轉到下标的to的結點下面，這裡的結點編号跟要維護的區間的下标是不一緻的

區間就是BST的中序序列，寫個find函數把區間下标對應的結點編号求出來

int findk(int k,int now)//找區間中第k個數字的下标(0是第一個)
{
    pushdown(now);//往下找之前要pushdown(可能左右子樹需要翻轉)
    if(k == siz[ls]+) return now;
    else if(k <= siz[ls]) return findk(k,ls);
    else return findk(k-siz[ls]-,rs);
}

上面也提到了，0是區間中的第一個數字，是以要splay的是L和R+2

void update(int L,int R)
{
    int &now = root;//為了用上面那個宏弄了個引用...(一開始沒寫引用狂T o(╥﹏╥)o)
    splay(findk(L,root),);
    splay(findk(R+,root),root);
    lazy[ch[rs][]] ^= ;
    pushup(rs);
    pushup(root);
}

完整代碼

#include<cstdio>
#include<algorithm>
using namespace std;

const int maxn =  + ;
int ch[maxn][], fa[maxn], val[maxn], siz[maxn], lazy[maxn];
int tot,root;
#define ls ch[now][0]
#define rs ch[now][1]
int N,M;
void newnode(int v,int &x,int f)
{
    x = ++tot;
    ch[x][] = ch[x][] = ;
    val[x] = v;
    siz[x] = ;
    lazy[x] = ;
    fa[x] = f;
}

bool get(int x)//傳回x是它父親的哪個兒子
{
    return x == ch[fa[x]][];
}

void pushup(int now)
{
    if(now)
        siz[now] = siz[ls] + siz[rs] + ;
}

void pushdown(int now)
{
    if(lazy[now])
    {
        lazy[ls] ^= ;
        lazy[rs] ^= ;
        swap(ls,rs);//翻轉把左右子樹交換一下就好了
        lazy[now] = ;
    }
}

void connect(int son,int f,int dir)
{
    fa[son] = f;
    ch[f][dir] = son;
}

int y,z,yson,zson,xson;
void Rotate(int x)//把x旋轉到fa[x]的位置,用get來判斷要左旋還是右旋
{
    y = fa[x];
    z = fa[y];
    yson = get(x), zson = get(y);//記錄x和y是他們父親的哪個兒子
    xson = ch[x][yson^];
    connect(x,z,zson);
    connect(y,x,yson^);
    connect(xson,y,yson);
    pushup(y);
}

void splay(int x,int to)//把x旋轉到to的下面
{
    pushdown(x);
    while(fa[x] != to)
    {
        if(fa[fa[x]] == to)
            Rotate(x);
        else if(get(x)==get(fa[x]))
            Rotate(fa[x]), Rotate(x);
        else
            Rotate(x), Rotate(x);
    }
    pushup(x);
    if(to == )//x移到根了，更新根
        root = x;
}

void build(int l,int r,int &now,int f)
{
    if(l>r) return ;
    int m = l + r >> ;
    newnode(m,now,f);
    build(l,m-,ls,now);
    build(m+,r,rs,now);
    pushup(now);
}

int findk(int k,int now)//找區間中第k個數字的下标(0是第一個)
{
    pushdown(now);
    if(k == siz[ls]+) return now;
    else if(k <= siz[ls]) return findk(k,ls);
    else return findk(k-siz[ls]-,rs);
}

void update(int L,int R)
{
    int &now = root;//為了用上面那個宏弄了個引用...(一開始沒寫引用狂T o(╥﹏╥)o)
    splay(findk(L,root),);
    splay(findk(R+,root),root);
    lazy[ch[rs][]] ^= ;
    pushup(rs);
    pushup(root);
}

void dfs(int now)
{
    pushdown(now);
    if(ls)
        dfs(ls);
    if(val[now]<=N&&val[now]>=)
        printf("%d ",val[now]);
    if(rs)
        dfs(rs);
}

int main()
{
    int l,r;
    scanf("%d%d",&N,&M);
    newnode(,root,);
    newnode(N+,ch[root][],root);
    build(,N,ch[ch[root][]][],ch[root][]);
    while(M--)
    {
        scanf("%d%d",&l,&r);
        update(l,r);
    }
    dfs(root);
    return ;
}

轉載于:https://www.cnblogs.com/Apale/p/9748784.html

上一篇: Mysql一些優化參數Mysql一些優化參數
下一篇: 【BZOJ 3223】文藝平衡樹