bzoj1507[NOI2003]Editor

bzoj1507[NOI2003]Editor

 

1507: [NOI2003]Editor

Time Limit: 5 Sec Memory Limit: 162 MB
Submit: 2685 Solved: 1066
[Submit][Status][Discuss]

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 15
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

HINT

 

Source

 

 

 

 

這道題和bzoj1269文本編輯器很像，方法都是Splay維護區間。

只需要將GET操作稍作修改就可以了。

注意這道題的INSERT操作可能分行輸入。

 

 

 

#include
#include
#include
#include
#include
#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
#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];
inline void pushup(int k)
{
	if (!k) return;
	s[k]=s[c[k][0]]+s[c[k][1]]+1;
}
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)
{
	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]=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 (l126) ch[i]=getchar();
	}
	split(pos+1,pos);
	ins(key,1,x,c[rt][1]);
	pushup(c[rt][1]);pushup(rt);
}
inline void solvedel()
{
	scanf("%d%*c",&x);
	split(pos+1,pos+x);
	fa[key]=0;key=0;
	pushup(c[rt][1]);pushup(rt);
}
inline void travel(int k)
{
	if (!k) return;
	travel(c[k][0]);
	printf("%c",v[k]);
	travel(c[k][1]);
}
inline void getans()
{
	scanf("%d%*c",&x);
	split(pos+1,pos+x);
	travel(key);printf("\n");
}
int main()
{
	newnode(rt,'*',0);newnode(c[rt][1],'*',rt);
	pushup(rt);
	scanf("%d%*c",&n);
	F(i,1,n)
	{
		scanf("%s%*c",op);
		if (op[0]=='M') {scanf("%d%*c",&x);pos=x+1;}
		else if (op[0]=='I') solveins();
		else if (op[0]=='D') solvedel();
		else if (op[0]=='G') getans();
		else if (op[0]=='P') pos--;
		else pos++;
	}
}