记录编号	356899	评测结果	AAAAAAAAAA
题目名称	[NOI 2003]文本编辑器	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	1.510 s
提交时间	2016-12-07 10:48:04	内存使用	4.56 MiB

#include <cstdio>
#include <cstdlib>
#include <cstdarg>
#include <algorithm>
#include <vector>
#include <cctype>
#include <queue>
#include <ctime>
using namespace std;
#define BT __attribute__((optimize("O3")))
struct node
{
    node *ls, *rs;
    int key, value;
    int size;
    #define SIZE(x) ((x)?(x)->size:0)
    inline node(int v):key(rand()), value(v)
    {
        ls = rs = NULL;
        size = 1;
    }
    inline void pushup()
    {
        size = 1+SIZE(ls)+SIZE(rs);
    }
};
typedef node *pnode;
typedef pair<node *, node *>droot;
BT
node *merge(node *a, node *b)
{
    if(!a)return b;
    if(!b)return a;
    if(a->key < b->key)
    {
        a->rs = merge(a->rs, b);
        a->pushup();
        return a;
    }else
    {
        b->ls = merge(a, b->ls);
        b->pushup();
        return b;
    }
}
BT
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;
}
BT
int kth(node *x, int k)
{
    if(!x || k > SIZE(x) || k <= 0)return 0;
    int s = SIZE(x->rs);
    if(k == s+1)return x->value;
    else if(k <= s)return kth(x->rs, k);
    else return kth(x->ls, k-s-1);
}
BT
int rank(node *x, int v)
{
    if(!x)return 0;
    if(v < x->value)
        return rank(x->ls, v);
    else
        return rank(x->rs, v)+SIZE(x->ls)+1;
}
BT
node* insert(node *root, int v)
{
    int k = rank(root, v);
    droot x = split(root, k);
    node *nd = new node(v);
    return merge(merge(x.first, nd), x.second);
}
BT
node *build(int *a, int n)
{
    pnode *stk = new pnode[n];
    node *last;
    int tp = 0;
    for(int i = 1; i <= n; i++)
    {
        node *p = new node(a[i]);
        last = NULL;
        while(tp && stk[tp-1]->key > p->key)
        {
            stk[tp-1]->pushup();
            last = stk[tp-1];
            stk[--tp] = NULL;
        }
        if(tp)stk[tp-1]->rs = p;
        p->ls = last;
        stk[tp++] = p;
    }
    while(tp)stk[--tp]->pushup();
    node *r = stk[0];
    delete []stk;
    return r;
}
char buf[1<<18], *fs, *ft;
BT
inline char readc()
{
    return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<18,stdin),fs==ft))?0:*fs++;
}
BT
int fast_read()
{
    int r;
    char c;
    bool s = false;
    while(c = readc())
    {
        if(c >= '0' && c <= '9')
        {
            r = c^0x30;
            break;
        }else if(c == '-')s = true;
    }
    while(isdigit(c = readc()))
        r = (r<<3)+(r<<1)+(c^0x30);
    return s?-r:r;
}
int tmp[1048579];
void readn(int n)
{
    char c;
    int p = 1;
    while(n)
    {
        c = readc();
        if(c < 32 || c > 126)continue;
        else tmp[p++] = c, n--;
    }
}
BT
void dfs(node *u)
{
    if(!u)return;
    dfs(u->ls);
    if(u->value >= 32 && u->value <= 126)
        putchar(u->value);
    dfs(u->rs);
}
inline void clear(int n)
{
    while(n--)readc();
}
int main()
{
    //freopen("test_data.txt", "r", stdin);
    freopen("editor2003.in", "r", stdin);
    freopen("editor2003.out", "w", stdout);
    srand(time(NULL));
    int cur = 0;
    int TS = fast_read();
    node *t = NULL;
    while(TS--)
    {
        char op;
        while(!isalpha(op = readc()));
        switch(op)
        {
            case 'M':
            {
                cur = fast_read();
            }break;
            case 'I':
            {
                int n = fast_read();
                readn(n);
                node *troot = build(tmp, n);
                if(!t)
                    t = troot;
                else
                {
                    droot ps = split(t, cur);
                    t = merge(ps.first, merge(troot, ps.second));
                }
            }break;
            case 'D':
            {
                int n = fast_read();
                droot ps = split(t, cur);
                droot ps2 = split(ps.second, n);
                t = merge(ps.first, ps2.second);
            }break;
            case 'G':
            {
                int n = fast_read();
                droot ps = split(t, cur);
                droot ps2 = split(ps.second, n);
                dfs(ps2.first);
                putchar('\n');
                t = merge(ps.first, merge(ps2.first, ps2.second));
            }break;
            case 'P':
            {
                cur--;
                clear(3);
            }break;
            case 'N':
            {
                cur++;
                clear(3);
            }break;
        }
    }
    return 0;
}