bzoj3223 Tyvj 1729 文藝平衡樹

3223: Tyvj 1729 文藝平衡樹

Time Limit: 10 Sec  Memory Limit: 128 MB

Submit: 5813  Solved: 3464

[Submit][Status][Discuss]

Description

您需要寫一種資料結構（可參考題目标題），來維護一個有序數列，其中需要提供以下操作：翻轉一個區間，例如原有序序列是5 4 3 2 1，翻轉區間是[2,4]的話，結果是5 2 3 4 1 

Input

第一行為n,m n表示初始序列有n個數，這個序列依次是(1,2……n-1,n)  m表示翻轉操作次數

接下來m行每行兩個數[l,r] 資料保證 1<=l<=r<=n 

Output

輸出一行n個數字，表示原始序列經過m次變換後的結果 

Sample Input

5 3

1 3

1 3

1 4

Sample Output

4 3 2 1 5

HINT

N,M<=100000

Source

平衡樹

分析：splay上的區間操作.

          一般的區間操作可以通過線段樹解決，但是有一部分區間操作隻能通過splay來解決.它在區間操作上和線段樹有相通的地方：build,pushup,pushdown這些操作基本上都差不多，但是又有一些細微的差異.

          以這題為例，先提取區間，将l-1轉到根節點，再将r+1轉到根節點的右節點.那麼根節點的右節點的左子樹就是要求的[l,r]區間.為了能夠友善的提取區間[1,n],加入兩個哨兵元素0,n + 1,那麼實際操作的就是l,r+2.

          翻轉操作可以變成逐層翻轉.就是将要翻轉的區間在splay中的每一個點的左右子樹交換，從上到下.為了提高效率，打個标記.那麼實際上的翻轉操作就都在pushdown中完成了.以後不管執行什麼操作，若是從上到下，執行到x就要pushdown(x),最後pushup(x).

          和線段樹的一些小差別：建樹是[l,mid - 1],[mid + 1,r],中間的mid不存在了.這樣做我個人認為是因為splay中每個點代表一個元素，而線段樹每個點代表一個區間. 在pushup的時候要加上目前節點的值！

          最後中序周遊一遍就出來了，這裡用到了一個原理：splay的中序周遊=原序列.

          幾個注意點：1.pushup注意順序！先子樹，後父親. 2.輸出判斷目前點是否是哨兵元素. 3.因為插入了哨兵元素，是以每個元素的位置都要往後挪1. 4.splay的最後不要輕易換根，因為這不是直接旋轉到根節點，而是旋轉到某個點的下面，要先判斷旋轉到的點是不是0，是的話才能換根.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int maxn = 200010;

int n,m,tot,root,sizee[maxn];

struct node
{
    int fa,left,right,v,tag;
}e[maxn];

void update(int x)
{
    sizee[x] = 1;
    if (e[x].left != 0)
        sizee[x] += sizee[e[x].left];
    if (e[x].right != 0)
        sizee[x] += sizee[e[x].right];
}

void pushdown(int x)
{
    if (!x)
        return;
    if (e[x].tag)
    {
        e[e[x].left].tag ^= 1;
        e[e[x].right].tag ^= 1;
        e[x].tag = 0;
        int t = e[x].left;
        e[x].left = e[x].right;
        e[x].right = t;
    }
}

int build(int l,int r) //感覺這個建樹不僅賦予了每個點代表的值，還标記了左右區間.
{
    if (l > r)
        return 0;
    int x = ++tot;
    int mid = (l + r) >> 1;
    e[x].fa = e[x].left = e[x].right = e[x].tag = 0;
    e[x].v = mid;
    sizee[x] = 1;
    e[x].left = build(l,mid - 1);
    e[x].right = build(mid + 1,r);
    e[e[x].left].fa = e[e[x].right].fa = x;
    update(x);
    return x;
}

void turnr(int x)
{
    pushdown(x);
    int y = e[x].fa;
    int z = e[y].fa;
    e[y].left = e[x].right;
    if (e[x].right != 0)
        e[e[x].right].fa = y;
    e[x].fa = z;
    if (z != 0)
    {
        if (e[z].left == y)
            e[z].left = x;
        else
            e[z].right = x;
    }
    e[x].right = y;
    e[y].fa = x;
    update(x);
    update(y);
}

void turnl(int x)
{
    pushdown(x);
    int y = e[x].fa;
    int z = e[y].fa;
    e[y].right = e[x].left;
    if (e[x].left != 0)
        e[e[x].left].fa = y;
    e[x].fa = z;
    if (z != 0)
    {
        if (e[z].left == y)
            e[z].left = x;
        else
            e[z].right = x;
    }
    e[x].left = y;
    e[y].fa = x;
    update(x);
    update(y);
}

void splay(int x,int yy)
{
    if (yy == 0)
        root = x;
    while (e[x].fa != yy)
    {
        pushdown(x);
        int y = e[x].fa;
        int z = e[y].fa;
        if (z == yy || z == 0)
        {
            if (x == e[y].left)
                turnr(x);
            else
                turnl(x);
        }
        else
        {
            if (e[z].left == y && e[y].left == x)
            {
                turnr(y);
                turnr(x);
            }
            else
            {
                if (e[z].right == y && e[y].right == x)
                {
                    turnl(y);
                    turnl(x);
                }
                else
                {
                    if (e[z].left == y && e[y].right == x)
                    {
                        turnl(x);
                        turnr(x);
                    }
                    else
                    {
                            turnr(x);
                            turnl(x);
                    }
                }
            }
        }
    }
    if (yy == 0)
        root = x;
}
int find(int x,int k)
{
    pushdown(x);
    if (k > sizee[e[x].left] + 1)
        return find(e[x].right,k - 1 - sizee[e[x].left]);
    if (k == sizee[e[x].left] + 1)
        return x;
    return find(e[x].left,k);
}

void dfs(int x)
{
    pushdown(x);
    if (e[x].left)
        dfs(e[x].left);
    if (e[x].v >= 1 && e[x].v <= n)
        printf("%d ",e[x].v);
    if (e[x].right)
        dfs(e[x].right);
}

int main()
{
    scanf("%d%d",&n,&m);
    root = build(0,n + 1);
    for (int i = 1; i <= m; i++)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        int p = find(root,l),q = find(root,r + 2);
        splay(p,0);
        splay(q,p);
        e[e[q].left].tag ^= 1;
        update(e[q].left);
        update(q);
        update(root);
    }
    dfs(root);

    return 0;
}      

轉載于:https://www.cnblogs.com/zbtrs/p/8270688.html