程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 1890 Robotic Sort 伸展樹的區間反轉與延遲標記

HDU 1890 Robotic Sort 伸展樹的區間反轉與延遲標記

編輯：C++入門知識

延遲標記像極了線段樹，不再多說。

區間反轉在樹伸展到位之後，也變成了簡單的遞歸交換左右兒子。

愈發感覺到伸展樹簡直太漂亮了，伸展操作更是誘惑到不行，總之數據結構太有魅力了。

比較簡單，就直接上模板了。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

#pragma comment(linker, "/STACK:1024000000");
#define EPS (1e-8)
#define LL long long
#define ULL unsigned long long
#define _LL __int64
#define _INF 0x3f3f3f3f
#define Mod 9999991

using namespace std;

const int MAXN = 100100;

struct N
{
    //info
    int son[2],pre,data;

    //data
    bool mark;
    int ls,rs,s;
} st[MAXN];

int Top;

struct W
{
    int data,site;
} num[MAXN],tnum[MAXN];

bool cmp(W a1,W a2)
{
    if(a1.data < a2.data)
        return true;
    if(a1.data == a2.data && a1.site < a2.site)
        return true;
    return false;
}

void Push_Down(int root)
{
    if(st[root].mark == 1)
    {
        st[root].mark = 0;
        if(st[root].son[0] != -1)
            st[st[root].son[0]].mark ^= 1;
        if(st[root].son[1] != -1)
            st[st[root].son[1]].mark ^= 1;

        int temp;
        temp = st[root].son[0];
        st[root].son[0] = st[root].son[1];
        st[root].son[1] = temp;

        temp = st[root].ls;
        st[root].ls = st[root].rs;
        st[root].rs = temp;
    }
}

void Updata(int root)
{
    st[root].ls = st[root].son[0] == -1 ? 0 : st[st[root].son[0]].s;
    st[root].rs = st[root].son[1] == -1 ? 0 : st[st[root].son[1]].s;
    st[root].s = st[root].ls + st[root].rs + 1;
}

void Init(int &root,int s,int e,int pre)
{
    if(s > e)
        return ;
    int mid = (s+e)>>1;

    root = Top++;
    st[root].son[0] = -1;
    st[root].son[1] = -1;
    st[root].pre = pre;
    st[root].data = num[mid].data;
    st[root].mark = 0;
    num[mid].site = root;

    Init(st[root].son[0],s,mid-1,root);
    Init(st[root].son[1],mid+1,e,root);

    Updata(root);
}

void Rotate(int root,int dir)
{
    st[st[root].pre].son[dir] = st[root].son[1^dir];
    st[root].son[1^dir] = st[root].pre;

    if(st[st[st[root].pre].pre].son[0] == st[root].pre)
        st[st[st[root].pre].pre].son[0] = root;
    else
        st[st[st[root].pre].pre].son[1] = root;
    int temp = st[root].pre;
    st[root].pre = st[st[root].pre].pre;
    st[temp].pre = root;

    if(st[temp].son[dir] != -1)
        st[st[temp].son[dir]].pre = temp;
    Updata(temp);
    Updata(root);
}

void Updata_Lazy(int root,int goal)
{
    if(st[root].pre != goal)
    {
        Updata_Lazy(st[root].pre,goal);
    }

    Push_Down(root);
}

int Splay(int root,int goal)
{
    Updata_Lazy(root,goal);

    while(st[root].pre != goal)
    {
        Rotate(root,(st[st[root].pre].son[0] == root ? 0 : 1));
    }

    return root;
}

int Search_Site(int root,int site)
{
    do
    {
        Push_Down(root);

        if(st[root].ls + 1 == site)
            return root;
        if(st[root].ls + 1 < site)
        {
            site = site - st[root].ls - 1;
            root = st[root].son[1];
        }
        else
            root = st[root].son[0];
    }while(1);
}


int main()
{
    int n;

    int i;

    int root,lsite,rsite;

    while(scanf("%d",&n) && n)
    {
        for(i = 2; i <= n+1; ++i)
        {
            scanf("%d",&tnum[i].data);
            num[i].site = i;
            tnum[i].site = i;
        }

        sort(tnum+2,tnum+n+2,cmp);

        num[1].data = 1,num[1].site = 1;
        num[n+2].data = n+2,num[n+2].site = n+2;

        for(i = 2; i <= n+1; ++i)
        {
            num[tnum[i].site].data = i;
        }

        root = -1,Top = 1;

        Init(root,1,n+2,0);

        st[0].son[0] = root,st[0].son[1] = -1;//虛擬父節點

        for(i = 2; i <= n+1; ++i)
        {
            root = Splay(num[tnum[i].site].site,0);

            printf("%d",st[root].ls);
            if(i == n+1) printf("\n");
            else printf(" ");

            lsite = min(st[root].ls+1,num[tnum[i].site].data)-1;
            rsite = max(st[root].ls+1,num[tnum[i].site].data)+1;
            lsite = Search_Site(root,lsite);
            rsite = Search_Site(root,rsite);
            root = Splay(rsite,0);
            root = Splay(lsite,0);
            st[st[st[root].son[1]].son[0]].mark ^= 1;
        }

    }
    return 0;
}