记录编号	359013	评测结果	AAAAAAAAAA
题目名称	[USACO Open09] 奶牛队列	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	0.108 s
提交时间	2016-12-20 13:37:18	内存使用	0.31 MiB

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <deque>
using namespace std;
struct node
{
    node *ls, *rs;
    int size;
    int fix, value;
    #define SIZE(x) ((x)?(x)->size:0)
    node(int v):fix(rand()), value(v)
    {
        size = 1;
        ls = rs = NULL;
    }
    inline void pushup()
    {
        size = 1+SIZE(ls)+SIZE(rs);
    }
};
node *merge(node *a, node *b)
{
    if(!a)return b;if(!b)return a;
    if(a->fix < b->fix)
    {
        a->rs = merge(a->rs, b);
        a->pushup();
        return a;
    }else
    {
        b->ls = merge(a, b->ls);
        b->pushup();
        return b;
    }
}
typedef pair<node *, node *>droot;
droot split(node *x, int k)
{
    if(!x)return droot(NULL, NULL);
    droot r;
    if(SIZE(x->ls) >= k)
    {
        r = split(x->ls, k);
        x->ls = r.second;
        x->pushup();
        r.second = x;
    }else
    {
        r = split(x->rs, k-SIZE(x->ls)-1);
        x->rs = r.first;
        x->pushup();
        r.first = x;
    }
    return r;
}
char a[3], b[3];
void dfs(node *x)
{
    if(!x)return;
    dfs(x->ls);
    printf("%d\n", x->value);
    dfs(x->rs);
}
int main()
{
    freopen("cline.in", "r", stdin);
    freopen("cline.out", "w", stdout);
    node *t = NULL;
    int m;scanf("%d", &m);
    int idx = 1;
    while(m--)
    {
        scanf(" %s %s", a, b);
        if(a[0] == 'A')
        {
            node *c = new node(idx++);
            if(b[0] == 'R')
            {
                t = merge(t, c);
            }else if(b[0] == 'L')
            {
                t = merge(c, t);
            }
        }else if(a[0] == 'D')
        {
            int n;scanf("%d", &n);
            if(b[0] == 'R')
            {
                t = split(t, t->size-n).first;   
            }else if(b[0] == 'L')
            {
                t = split(t, n).second;
            }
        }
    }
    dfs(t);
    return 0;
}