HDU 3487 Play with Chain | Splay

Play with Chain

Time Limit: 6000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)

Problem Description

YaoYao is fond of playing his chains. He has a chain containing n diamonds on it. Diamonds are numbered from 1 to n. At first, the diamonds on the chain is a sequence: 1, 2, 3, …, n. He will perform two types of operations:

CUT a b c: He will first cut down the chain from the ath diamond to the bth diamond. And then insert it after the cth diamond on the remaining chain. For example, if n=8, the chain is: 1 2 3 4 5 6 7 8; We perform “CUT 3 5 4”, Then we first cut down 3 4 5, and the remaining chain would be: 1 2 6 7 8. Then we insert “3 4 5” into the chain before 5th diamond, the chain turns out to be: 1 2 6 7 3 4 5 8.

FLIP a b: We first cut down the chain from the ath diamond to the bth diamond. Then reverse the chain and put them back to the original position. For example, if we perform “FLIP 2 6” on the chain: 1 2 6 7 3 4 5 8. The chain will turn out to be: 1 4 3 7 6 2 5 8

He wants to know what the chain looks like after perform m operations. Could you help him?

Input

There will be multiple test cases in a test data. For each test case, the first line contains two numbers: n and m (1≤n, m≤3*100000), indicating the total number of diamonds on the chain and the number of operations respectively. Then m lines follow, each line contains one operation. The command is like this: CUT a b c // Means a CUT operation, 1 ≤ a ≤ b ≤ n, 0≤ c ≤ n-(b-a+1). FLIP a b // Means a FLIP operation, 1 ≤ a < b ≤ n. The input ends up with two negative numbers, which should not be processed as a case.

Output

For each test case, you should print a line with n numbers. The ith number is the number of the ith diamond on the chain.

Sample Input

8 2
CUT 3 5 4
FLIP 2 6
-1 -1

Sample Output

1 4 3 7 6 2 5 8

题意

给出一列数，然后对整个数列执行两种操作：切下一段插入到另外的位置，或者把其中的一整段整个翻转一下。

求经过一系列操作之后，数列最后的样子。

分析

数据范围最高能够到达3e5那么大，因此算法至少要是O(nlogn)复杂度以下才可能达到要求。

考虑采用Splay解决（这样的题目只能用这种动态维护的树结构不是么？）

初始先建树，把1~n加入Splay树。由于数列在后面是要被打乱顺序的，Splay二叉平衡树的性质只有在初始的时候是被保持的，之后是靠size，即每个点在中序遍历中的位置来维护。最后输出数列则只需要中序遍历一遍即可。

切割操作：若要切下ab段，则把第a-1个结点移到根，把第b+1个结点移到根以下（即跟的右子树），则整个ab段就落在b+1的左子树上，切出来。插入到c的时候，将c移到根，c+1移到根的右子树，则切出来的插入到c+1的左子树即可

翻转操作：用上面相同的方法把a~b整合到一棵子树上，然后可以参考线段树标记的方法，通过标记来完成访问结点的翻转等操作。

具体可以在纸上模拟一下……

教训

教训还是比较惨痛的…卡在这道题上好久了。

首先是输入输出以后要特别注意结尾方式，两个负数结尾还是两个-1结尾

把各种可能出现的不同情况考虑完整

/* ***********************************************
MYID    : Chen Fan
LANG    : G++
PROG    : HDU3487
************************************************ */

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

using namespace std;

#define MAXN 300010

int sons[MAXN][2];
int father[MAXN],size[MAXN],data[MAXN],list[MAXN];
bool flag[MAXN];
int spt=0,spttail=0;

void down(int x)
{
    if (flag[x])
    {
        flag[x]=0;
        swap(sons[x][0],sons[x][1]);
        flag[sons[x][0]]^=1;
        flag[sons[x][1]]^=1;
    }
}

void rotate(int x,int w) //rotate(node,0/1)
{
    int y=father[x];
    down(y);down(x);
    sons[y][!w]=sons[x][w];
    if (sons[x][w]) father[sons[x][w]]=y;

    father[x]=father[y];
    if (father[y]) sons[father[y]][y==sons[father[y]][1]]=x;

    sons[x][w]=y;
    father[y]=x;

    size[x]=size[y];
    size[y]=size[sons[y][0]]+size[sons[y][1]]+1;
}

void splay(int x,int y) //splay(node,position)
{
    down(x);
    while(father[x]!=y)
    {
        if (father[father[x]]==y) rotate(x,x==sons[father[x]][0]);
        else 
        {
            int t=father[x];
            int w=(sons[father[t]][0]==t);
            if (sons[t][w]==x)
            {
                rotate(x,!w);
                rotate(x,w);
            } else 
            {
                rotate(t,w);
                rotate(x,w);
            }
        }
    }
    if (!y) spt=x;
}

void select(int x,int v,int p) //select(root,k,position)
{
    down(x);
    while(v!=size[sons[x][0]]+1)
    {
        if (v<=size[sons[x][0]]) 
        {
            x=sons[x][0];
            down(x);
        }
        else 
        {
            v-=size[sons[x][0]]+1;
            x=sons[x][1];
            down(x);
        }
    }
    splay(x,p);
}

bool done=false;

void outp(int x)
{
    down(x);
    if (sons[x][0]) outp(sons[x][0]);
    if (done) printf(" ");
    done=true;
    printf("%d",data[x]);
    if (sons[x][1]) outp(sons[x][1]);
}

void maketree(int l,int r)
{
    spttail++;
    int now=spttail,w=(l+r)/2,ls=0,rs=0;
    data[now]=w;
    flag[now]=false;
    sons[now][0]=0;
    sons[now][1]=0;
    
    if (l<=w-1)
    {
        ls=spttail+1;
        sons[now][0]=ls;
        father[ls]=now;
        maketree(l,w-1);
    }
    if (w+1<=r)
    {
        rs=spttail+1;
        sons[now][1]=rs;
        father[rs]=now;
        maketree(w+1,r);
    }

    size[now]=size[ls]+size[rs]+1;
}

int main()
{
    freopen("3487.txt","r",stdin);
    
    int n,m;
    scanf("%d%d",&n,&m);
    while(!(n<0&&m<0))
    {
        spt=1;
        spttail=0;
        father[1]=0;
        maketree(1,n);

        for (int i=1;i<=m;i++)
        {
            char s[10];
            scanf("%s",&s);
            if (s[0]=='C')
            {
                int a,b,c,temp;
                scanf("%d%d%d",&a,&b,&c);

                if (a>1)
                {
                    select(spt,a-1,0);
                    if (b<n)
                    {
                        select(spt,b+1,spt);
                        temp=sons[sons[spt][1]][0];
                        sons[sons[spt][1]][0]=0;
                        size[spt]-=size[temp];
                        size[sons[spt][1]]-=size[temp];
                    } else 
                    {
                        temp=sons[spt][1];
                        sons[spt][1]=0;
                        size[spt]-=size[temp];
                    }
                } else 
                {
                    if (b<n)
                    {
                        select(spt,b+1,0);
                        temp=sons[spt][0];
                        sons[spt][0]=0;
                        size[spt]-=size[temp];
                    } else temp=spt;
                }

                if (c>0)
                {
                    select(spt,c,0);
                    if (c==size[spt])
                    {
                        sons[spt][1]=temp;
                        father[temp]=spt;
                        size[spt]+=size[temp];
                    } else
                    {
                        select(spt,c+1,spt);
                        sons[sons[spt][1]][0]=temp;
                        father[temp]=sons[spt][1];
                        size[spt]+=size[temp];
                        size[sons[spt][1]]+=size[temp];
                    }
                } else 
                {
                    if (spt!=temp)
                    {
                        select(spt,1,0);
                        sons[spt][0]=temp;
                        father[temp]=spt;
                        size[spt]+=size[temp];
                    }
                }  
            } else 
            {
                int a,b,temp;
                scanf("%d%d",&a,&b);
                if (a>1)
                {
                    select(spt,a-1,0);
                    if (b<n)
                    {
                        select(spt,b+1,spt);
                        temp=sons[sons[spt][1]][0];
                    } else 
                    {
                        temp=sons[spt][1];
                    }
                } else 
                {
                    if (b<n)
                    {
                        select(spt,b+1,0);
                        temp=sons[spt][0];
                    } else temp=spt;
                }
                flag[temp]^=1;
            }
        }
        done=false;
        outp(spt);
        printf("\n");
        scanf("%d%d",&n,&m);
    }

    return 0;
}