【Splay】 HDU 1890 Robotic Sort 翻转

点击打开链接

输入N个数

输出N个数

每次输出 P=值最小的位置  , 然后翻转 i-P 间的数

翻转操作用lazy标记

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
#include <queue>
#include <stack>
#include <vector>
#include <list>
#include <deque>
#include <set>
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <map>
typedef long long LL;
const int INF = 1<<29;
const LL mod = 1e9+7;
const int MAXN = 100050;
struct node
{
    int val,wei;
} p[MAXN];

bool cmp(node a,node b)
{
    if(a.val==b.val) return a.wei<b.wei;
    return a.val<b.val;
}
struct SPLAY
{
    int pre[MAXN],key[MAXN],ch[MAXN][2],size[MAXN],lazy[MAXN],root,tol;

    void init()
    {
        root=0,tol=0;
        ch[root][0]=ch[root][1]=0;
    }
    void NewNode(int &r,int father,int k)
    {
        r= ++tol;
        pre[r]=father;
        size[r]=1;
        lazy[r]=0;
        ch[r][0]=ch[r][1]=0;
    }
    void rev(int r)
    {
        if(!r) return ;
        swap(ch[r][0],ch[r][1]);
        lazy[r]^=1;
    }
    void pushup(int w)
    {
        size[w]=size[ch[w][0]]+size[ch[w][1]]+1;
    }
    void pushdown(int w)
    {
        if(lazy[w])
        {
            rev(ch[w][0]);
            rev(ch[w][1]);
            lazy[w]=0;
        }
    }
    void Rotate(int x,int kind)//0为左旋，1为右旋
    {
        int y=pre[x];
        pushdown(y);
        pushdown(x);
        ch[y][!kind]=ch[x][kind];
        pre[ch[x][kind]]=y;
        if(pre[y])
            ch[pre[y]][ch[pre[y]][1]==y]=x;
        pre[x]=pre[y];
        ch[x][kind]=y;
        pre[y]=x;
        pushup(y);
        pushup(x);
    }
    //Splay调整，将r节点调整为goal的儿子
    void Splay(int r,int goal)
    {
        while(pre[r]!=goal)
        {
            if(pre[pre[r]]==goal)
                Rotate(r,ch[pre[r]][0]==r);
            else
            {
                int y=pre[r];
                int kind=ch[pre[y]][0]==y;
                if(ch[y][kind]==r)
                {
                    Rotate(r,!kind);
                    Rotate(r,kind);
                }
                else
                {
                    Rotate(y,kind);
                    Rotate(r,kind);
                }
            }
        }
        if(goal==0) root=r;
    }
    int Get_k(int r,int k)
    {
        pushdown(r);
        int t=size[ch[r][0]]+1;
        if(t==k) return r;
        else if(k<t) return Get_k(ch[r][0],k);
        else return Get_k(ch[r][1],k-t);
    }
    int Get_next(int r)
    {
        pushdown(r);
        if(ch[r][1]==0) return -1;
        r=ch[r][1];
        while(ch[r][0])
        {
            r=ch[r][0];
            pushdown(r);
        }
        return r;
    }
    void gao(int n)
    {
        int a,b;
        for(int i=1; i<=n; i++)
        {
            scanf("%d",&p[i].val);
            p[i].wei=i+1;
        }
        sort(p+1,p+n+1,cmp);
        NewNode(root,0,1);
        for(int i=1; i<=n; i++)
        {
            NewNode(ch[i][1],i,i-1);
        }
        NewNode(ch[n+1][1],n+1,n+2);
        for(int i=n+1; i>=1; i--)
            pushup(i);
        for(int i=1;i<=n;i++)
        {
            Splay(p[i].wei,0);
//            for(int j=1;j<=n+2;j++)
//                printf("%d :%d %d\n",j,ch[j][0],ch[j][1]);
            printf("%d%c",size[ch[root][0]],i==n?'\n':' ');
            Splay(Get_k(root,i),0);
            Splay(Get_next(p[i].wei),root);
            rev(ch[ch[root][1]][0]);
        }
    }
} s;
int main()
{
    int n,m;
    while(scanf("%d",&n),n)
    {
        s.init();
        s.gao(n);
    }
    return 0;
}