1269: [AHOI2006]文本編輯器editor

Time Limit: 10 Sec Memory Limit: 162 MB

    Submit: 2678 Solved: 996

    [Submit][Status][Discuss]

Description

    這些日子，可可不和卡卡一起玩了，原來可可正廢寢忘食的想做一個簡單而高效的文本編輯器，

bzoj1269[AHOI2006]文本編輯器editor

。你能幫助他嗎？為了明確任務(wù)目標(biāo)，可可對“文本編輯器”做了一個抽象的定義：文本：由0個或多個字符構(gòu)成的序列。這些字符的ASCII碼在閉區(qū)間[32, 126]內(nèi)，也就是說，這些字符均為可見字符或空格。光標(biāo)：在一段文本中用于指示位置的標(biāo)記，可以位于文本的第一個字符之前，文本的最后一個字符之后或文本的某兩個相鄰字符之間。文本編輯器：為一個可以對一段文本和該文本中的一個光標(biāo)進(jìn)行如下七條操作的程序。如果這段文本為空，我們就說這個文本編輯器是空的。 編寫一個程序： 建立一個空的文本編輯器。 從輸入文件中讀入一些操作指令并執(zhí)行。 對所有執(zhí)行過的GET操作，將指定的內(nèi)容寫入輸出文件。

Input

    輸入文件中第一行是指令條數(shù)N，以下是需要執(zhí)行的N個操作。除了回車符之外，輸入文件的所有字符的ASCII碼都在閉區(qū)間[32, 126]內(nèi)。且行尾沒有空格。

Output

    依次對應(yīng)輸入文件中每條GET指令的輸出，不得有任何多余的字符。

Sample Input

10

    Insert 13

    Balanced eert

    Move 2

    Delete 5

    Next

    Insert 7

    editor

    Move 0

    Get

    Move 11

    Rotate 4

    Get

   

Sample Output

B

    t

   

HINT

    對輸入數(shù)據(jù)我們有如下假定： MOVE操作不超過50 000個，INSERT、DELETE和ROTATE操作作的總個數(shù)不超過6 000，GET操作不超過20 000個，PREV和NEXT操作的總個數(shù)不超過20 000。 所有INSERT插入的字符數(shù)之和不超過2M（1M=1 024*1 024）。 DELETE操作、ROTATE操作和GET操作執(zhí)行時光標(biāo)后必然有足夠的字符。MOVE、PREV、NEXT操作不會把光標(biāo)移動到非法位置。 輸入文件沒有錯誤。

Source

    鳴謝seter重新制作數(shù)據(jù)

    這道題很顯然是一道Splay維護(hù)區(qū)間題，只不過這里的值是字符而不是整數(shù)，其實道理是一樣的。

    我最初提交時輸入寫scanf(“%d\n”,&n)結(jié)果是TLE，后來改成scanf(“%d%*c”,&n)結(jié)果就對了，

電腦資料

《bzoj1269[AHOI2006]文本編輯器editor》(http://www.szmdbiao.com)。

    注：在scanf中如果%后加*表示讀入后不賦給相應(yīng)的變量，即跳過該輸入值。

#include<iostream>#include<cstdio>#include<cstdlib>#include<cmath>#include<cstring>#include#define F(i,j,n) for(int i=j;i<=n;i++)#define D(i,j,n) for(int i=j;i>=n;i--)#define LL long long#define pa pair<int,int>#define MAXN 2100000#define INF 1000000000#define key c[c[rt][1]][0]using namespace std;int pos=1,rt=0,tot=0,n,x,c[MAXN][2],s[MAXN],fa[MAXN];char v[MAXN],op[10],ch[MAXN];bool rev[MAXN];inline void pushup(int k){	if (!k) return;	s[k]=s[c[k][0]]+s[c[k][1]]+1;}inline void update(int k){	if (!k) return;	rev[k]^=1;	swap(c[k][0],c[k][1]);}inline void pushdown(int k){	if (!k) return;	if (rev[k])	{		update(c[k][0]);update(c[k][1]);		rev[k]=0;	}}inline void rotate(int x,int &k){	int y=fa[x],z=fa[y],l=(c[y][1]==x),r=l^1;	if (y==k) k=x;	else c[z][c[z][1]==y]=x;	fa[x]=z;fa[y]=x;fa[c[x][r]]=y;	c[y][l]=c[x][r];c[x][r]=y;	pushup(y);pushup(x);}inline void splay(int x,int &k){	while (x!=k)	{		int y=fa[x],z=fa[y];		if (y!=k)		{			if ((c[y][0]==x)^(c[z][0]==y)) rotate(x,k);			else rotate(y,k);		}		rotate(x,k);	}}inline int find(int k,int rank){	pushdown(k);	int l=c[k][0],r=c[k][1];	if (s[l]+1==rank) return k;	else if (s[l]>=rank) return find(l,rank);	else return find(r,rank-s[l]-1);}inline void split(int l,int r){	int x=find(rt,l-1),y=find(rt,r+1);	splay(x,rt);splay(y,c[rt][1]);}inline void newnode(int &k,char ch,int last){	k=++tot;	fa[k]=last;	v[k]=ch;	c[k][0]=c[k][1]=rev[k]=0;	s[k]=1;}inline void ins(int &k,int l,int r,int last){	int mid=(l+r)>>1;	newnode(k,ch[mid],last);	if (l<mid) else="" if="" inline="" int="" key="0;"" pos="x+1;}" pre="" void=""></p></mid)></int,int></cstring></cmath></cstdlib></cstdio></iostream>