網上這個題大多數的題解都是基於塊狀鏈表的，我的方法是用伸展樹Splay。Splay這個東西真是太強大了，靈活得令我五體投地。還是NB的Splay操作，就是把任意一個節點提到根位置。

首先建立一棵伸展樹，要記錄size以便快速定位。爲了方便，在樹中插入一個虛擬的頭節點，以後每次Move到第k個字符之後只需變成把第k+1個元素Splay到根位置。以後根結點就是光標位置了（光標前面的一個元素）。

插入一段字符串，要先把這段字符串建成一個Splay，怎麼建都行，我是把它猥瑣地建成了一條鏈。如果當前光標位置是最後一位，直接把新建 的樹接到根節點右子樹。否則把根結點的後繼節點Splay到根節點右子樹的根位置，接下來把新建的樹接到根節點右子樹根節點的左子樹下面。這種插入的方法 常數較小，時間複雜度爲O(L*logN)。要注意維護size。

刪除也很容易，如果根結點的位置爲k，要刪除的長度爲len，把第k+len+1這個元素Splay到根結點的右子樹根位置，然後把它的左子樹刪掉就行了。特殊的，如果第k+len+1個元素不存在，只需把根節點的右子樹全部刪除。

輸出一段字符串可以效仿刪除，只不過不用刪掉，而是把它輸出出來。極不建議用遞歸實現中序遍歷的輸出，因爲Splay可能很不平衡，這樣有 可能爆掉系統堆棧，所以要手動模擬棧實現。但是這種方法有些複雜了，其實可以一個一個得查找出來輸出，經嘗試這樣不會增加很多的運行時間，卻使程序縮短了 不少。

我寫了3.5K代碼，230行程序，還不算太長，不過運行起來要比塊狀鏈表快多了，所有數據都在0.8s內跑過了，10個測試點總運行時間爲3.5s。

/* 
 * Problem: NOI2003 editor
 * Author: Guo Jiabao
 * Time: 2009.5.17 16:56
 * State: Solved
 * Memo: Splay 線性建樹插入 線性輸出
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
const int MAXS=1024*1024*2;
struct SplayTree
{
    struct SplayNode
    {
        SplayNode *left,*right,*father;
        int size,value;
        int lsize() {return left?left->size:0;}
        int rsize() {return right?right->size:0;}
    };
    SplayNode *root,SS[MAXS],*Stack[MAXS];
    int SC,Spos[MAXS];
    SplayNode* newSplayNode(int value,SplayNode *f)
    {
        SS[SC].left = SS[SC].right = 0;
        SS[SC].father = f;
        SS[SC].size = 1;
        SS[SC].value = value;
        SC++;
        return SS+SC-1;
    }
    void init()
    {
        SC=0;
        root=newSplayNode('#',0);
    }
    void Update(SplayNode *x)
    {
        x->size=x->lsize() + x->rsize() + 1;
    }
    void Zig(SplayNode *x)
    {
        SplayNode *y=x->father;
        y->left=x->right;
        if (x->right)
            x->right->father=y;
        x->father=y->father;
        if (y->father)
        {
            if (y->father->left==y)
                y->father->left=x;
            else
                y->father->right=x;
        }
        y->father=x;
        x->right=y;
        Update(y);
        Update(x);
    }
    void Zag(SplayNode *x)
    {
        SplayNode *y=x->father;
        y->right=x->left;
        if (x->left)
            x->left->father=y;
        x->father=y->father;
        if (y->father)
        {
            if (y->father->left==y)
                y->father->left=x;
            else
                y->father->right=x;
        }
        y->father=x;
        x->left=y;
        Update(y);
        Update(x);
    }
    void Splay(SplayNode *x,SplayNode *f)
    {
        while (x->father != f)
        {
            if (x->father->father == f)
            {
                if (x == x->father->left)
                    Zig(x);
                else
                    Zag(x);
            }
            else if (x->father->father->left == x->father)
            {
                if (x == x->father->left)
                    Zig(x->father),Zig(x);
                else
                    Zag(x),Zig(x);
            }
            else
            {
                if (x == x->father->right)
                    Zag(x->father),Zag(x);
                else
                    Zig(x),Zag(x);
            }
        }
        if (f==0)
            root=x;
    }
    void Select(int k,SplayNode *f)
    {
        SplayNode *x=root;
        for (int l;k!= (l=x->lsize()) + 1 ;)
        {
            if (k <= l)
                x=x->left;
            else
            {
                k-=l+1;
                x=x->right;
            }
        }
        Splay(x,f);
    }
    void Insert(int *Str,int len)
    {
        SplayNode *x=newSplayNode(Str[1],0),*r,*y;
        r=x;
        for (int i=2;i<=len;i++)
        {
            x->right = newSplayNode(Str[i],x);
            x=x->right;
        }
        if (root->right)
        {
            Select(root->lsize()+2,root);
            y=root->right;
            y->left = r;
        }
        else
        {
            y=root;
            y->right=r;
        }
        r->father = y;
        for (;x;x=x->father)
            Update(x);
    }
    void Delete(int len)
    {
        if (root->lsize() + 2 + len <= root->size)
        {
            Select(root->lsize() + 2 + len,root);
            root->right->left=0;
            Update(root->right);
        }
        else
            root->right=0;
        Update(root);
    }
    void Get(int len)
    {
        SplayNode *x=root;
        int k=x->lsize()+1;
        for (int i=1;i<=len;i++)
        {
            Select(k+i,root);
            putchar(root->right->value);
        }
        putchar('\n');
    }
}Splay;
int N,Str[MAXS],Position;
void init()
{
    freopen("editor2003.in","r",stdin);
    freopen("editor2003.out","w",stdout);
    scanf("%d",&N);
    Splay.init();
}
void solve()
{
    int i,c,t,l;
    char Cmd[10];
    for (i=1;i<=N;i++)
    {
        while ((c=getchar())==10 || c==13);ungetc(c,stdin);
        for (t=0;(c=getchar())!=' ' && c!=10 && c!=13;)
            Cmd[++t]=c;
        switch (Cmd[1])
        {
            case 'M':
                scanf("%d",&t);
                Splay.Select(t+1,0);
                Position=t+1;
                break;
            case 'P':
                Splay.Select(--Position,0);
                break;
            case 'N':
                Splay.Select(++Position,0);
                break;
            case 'I':
                scanf("%d",&l);
                for (t=0;t<l;)
                {
                    while ((c=getchar())==10 || c==13);
                    Str[++t]=c;
                }
                Splay.Insert(Str,l);
                break;
            case 'D':
                scanf("%d",&l);
                Splay.Delete(l);
                break;
            case 'G':
                scanf("%d",&l);
                Splay.Get(l);
                break;
        }
    }
}
int main()
{
    init();
    solve();
    return 0;
}