Description
Input
输入文件editor.in的第一行是指令条数t，以下是需要执行的t个操作。其中： 为了使输入文件便于阅读，Insert操作的字符串中可能会插入一些回车符，请忽略掉它们（如果难以理解这句话，可以参考样例）。 除了回车符之外，输入文件的所有字符的ASCII码都在闭区间[32, 126]内。且行尾没有空格。 这里我们有如下假定：MOVE操作不超过50000个，INSERT和DELETE操作的总个数不超过4000，PREV和NEXT操作的总个数不超过200000。所有INSERT插入的字符数之和不超过2M（1M=1024*1024），正确的输出文件长度不超过3M字节。DELETE操作和GET操作执行时光标后必然有足够的字符。MOVE、PREV、NEXT操作必然不会试图把光标移动到非法位置。输入文件没有错误。 对C++选手的提示：经测试，最大的测试数据使用fstream进行输入有可能会比使用stdio慢约1秒。
Output
输出文件editor.out的每行依次对应输入文件中每条GET指令的输出。
Sample Input
15
Insert 26
abcdefghijklmnop
qrstuv wxy
Move 16
Delete 11
Move 5
Insert 1
^
Next
Insert 1
_
Next
Next
Insert 4
.\/.
Get 4
Prev
Insert 1
^
Move 0
Get 22
Insert 26
abcdefghijklmnop
qrstuv wxy
Move 16
Delete 11
Move 5
Insert 1
^
Next
Insert 1
_
Next
Next
Insert 4
.\/.
Get 4
Prev
Insert 1
^
Move 0
Get 22
Sample Output
.\/.
abcde^_^f.\/.ghijklmno
abcde^_^f.\/.ghijklmno
HINT
splay区间操作的裸题，就当是练习模板吧！
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
using namespace std;
int t,a,p = ;
char cmd[],s[*+];
class Splay
{
private:
struct Node
{
char ch;int size,cnt;Node *c[],*fa;
Node (char _ch,Node *_fa)
{
ch = _ch; fa = _fa;
cnt = ; c[] = c[] = NULL;
}
int lsz(){return c[]?c[]->size:;}
int rsz(){return c[]?c[]->size:;}
};
Node *root;
inline void upd(Node *tag)
{
if (!tag) return;
tag->size = tag->cnt+tag->lsz()+tag->rsz();
}
inline void zig(Node *tag,int d)
{
Node *f = tag -> fa;
int anti = d^;
f -> c[d] = tag->c[anti];
if (f->c[d])
f -> c[d] -> fa = f;
tag -> fa = f -> fa;
if (tag -> fa -> c[] == f)
tag -> fa -> c[] = tag;
else tag -> fa -> c[] = tag;
f -> fa = tag;
tag -> c[anti] = f;
upd(f);
}
inline bool f(Node *tag){return tag->fa->c[] == tag;}
inline void splay(Node *tag,Node *goal)
{
while(tag->fa != goal){
if(tag->fa->fa == goal)
zig(tag,f(tag));
else{
if(f(tag) == f(tag->fa))
zig(tag->fa,f(tag->fa)),zig(tag,f(tag));
else
zig(tag,f(tag)),zig(tag,f(tag));
}
}
upd(tag);
}
inline Node *search(int key)
{
Node *tag = root->c[];
while (tag && (key <= tag->lsz()||key > tag -> lsz() + tag -> cnt))
{
if (key > tag ->lsz()+tag->cnt)
{
key -= tag->lsz()+tag->cnt; tag = tag->c[];
}
else tag = tag -> c[];
}
return tag;
}
public:
Splay()
{
root = new Node('#',NULL); Node *tmp = new Node('^',root); root ->c[] = tmp; upd(tmp);
}
void insert(char *s)
{
Node *chr = new Node(s[],NULL),*tmp,*now,*tag = root->c[];
tmp = now = chr; chr -> size = a;
for (int i = ;i < a;++i)
{
now = new Node(s[i],tmp);
tmp -> c[] = now; now -> size = a-i;
tmp = now;
}
Node *z = tag -> c[];
while (z && z->c[]) z = z->c[];
if (z)
{
splay(z,tag);
z -> c[] = chr; chr -> fa = z;
upd(z);
}
else
{
tag -> c[] = chr; chr -> fa = tag;
upd(tag);
}
}
void trans(int x) {Node *tag = search(x); splay(tag,root);}
void erase(int l)
{
Node *tag = root->c[]; if (!tag) return;
Node *end = search(tag->lsz()+tag->cnt+l+);
if (end){splay(end,tag); end -> c[] = NULL; upd(end);}
else tag -> c[] = NULL;
upd(tag);
}
void print(int l)
{
Node *tag = root->c[];
for (int i = ;i <= l;++i)
{
Node *tmp = search(p+i);
splay(tmp,tag);
putchar(tmp -> ch);
}
putchar('\n');
}
}tree;
int main()
{
freopen("1507.in","r",stdin);
freopen("1507.out","w",stdout);
scanf("%d",&t);
while (t--)
{
scanf("%s %d",cmd,&a);
if (cmd[] == 'I')
{
char c;
for (int i = ;i<a;)
{
while ((c = getchar())==||c == );
s[i++] = c;
}
tree.insert(s); continue;
}
if (cmd[] == 'M')
{
tree.trans(a+); p = a + ; continue;
}
if (cmd[] == 'D')
{
tree.erase(a); continue;
}
if (cmd[] == 'G')
{
tree.print(a); continue;
}
if (cmd[] == 'P')
{
tree.trans(--p); continue;
}
if(cmd[] == 'N')
{
tree.trans(++ p); continue;
}
}
fclose(stdin); fclose(stdout);
return ;
}