HYSBZ 1269 文本編輯器editor

Description

這些日子，可可不和卡卡一起玩了，原來可可正廢寝忘食的想做一個簡單而高效的文本編輯器。你能幫助他嗎？為了明确任務目标，可可對“文本編輯器”做了一個抽象的定義： 

 文本：由0個或多個字元構成的序列。這些字元的ASCII碼在閉區間[32, 126]内，也就是說，這些字元均為可見字元或空格。光标：在一段文本中用于訓示位置的标記，可以位于文本的第一個字元之前，文本的最後一個字元之後或文本的某兩個相鄰字元之間。文本編輯器：為一個可以對一段文本和該文本中的一個光标進行如下七條操作的程式。如果這段文本為空，我們就說這個文本編輯器是空的。 編寫一個程式： 建立一個空的文本編輯器。 從輸入檔案中讀入一些操作指令并執行。 對所有執行過的GET操作，将指定的内容寫入輸出檔案。

Input

輸入檔案中第一行是指令條數N，以下是需要執行的N個操作。除了回車符之外，輸入檔案的所有字元的ASCII碼都在閉區間[32, 126]内。且行尾沒有空格。

Output

依次對應輸入檔案中每條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

對輸入資料我們有如下假定： MOVE操作不超過50 000個，INSERT、DELETE和ROTATE操作作的總個數不超過6 000，GET操作不超過20 000個，PREV和NEXT操作的總個數不超過20 000。 所有INSERT插入的字元數之和不超過2M（1M=1 024*1 024）。 DELETE操作、ROTATE操作和GET操作執行時光标後必然有足夠的字元。MOVE、PREV、NEXT操作不會把光标移動到非法位置。 輸入檔案沒有錯誤。

這題操作比較多，但其實都是splay的經典操作，熟練掌握以後條理就很清晰了，寫的也很簡單。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<iostream>
#include<algorithm>
#include<bitset>
#include<functional>
using namespace std;
typedef unsigned long long ull;
typedef long long LL;
const int maxn = 3e6;
int T, root, x;
char s[maxn];

struct Splays
{
	const static int maxn = 3e6;			//節點個數
	const static int INF = 0x7FFFFFFF;			//int最大值
	int ch[maxn][2], F[maxn], sz;				//左右兒子，父親節點和節點總個數
	int C[maxn], R[maxn];
	char S[maxn];
	int Node(int f, char s) { S[sz] = s; C[sz] = 1; R[sz] = ch[sz][0] = ch[sz][1] = 0; F[sz] = f; return sz++; }//申請一個新節點
	void clear(){ sz = 1; ch[0][0] = ch[0][1] = F[0] = 0; C[0] = 0; }//清空操作
	void pushdown(int x)
	{
		if (!R[x]) return;
		R[ch[x][0]] ^= 1;	R[ch[x][1]] ^= 1;
		swap(ch[x][0], ch[x][1]);	R[x] = 0;
	}
	void rotate(int x, int k)
	{
		int y = F[x]; ch[y][!k] = ch[x][k]; F[ch[x][k]] = y;
		if (F[y]) ch[F[y]][y == ch[F[y]][1]] = x;
		F[x] = F[y];    F[y] = x;	ch[x][k] = y;
		C[x] = C[y];	C[y] = C[ch[y][0]] + C[ch[y][1]] + 1;
	}
	void Splay(int x, int r)
	{
		for (int fa = F[r]; F[x] != fa;)
		{
			if (F[F[x]] == fa) { rotate(x, x == ch[F[x]][0]); return; }
			int y = x == ch[F[x]][0], z = F[x] == ch[F[F[x]]][0];
			y^z ? (rotate(x, y), rotate(x, z)) : (rotate(F[x], z), rotate(x, y));
		}
	}
	void build(int fa, int &x, int l, int r, char *s)
	{
		if (l > r) return;
		int mid = l + r >> 1;
		x = Node(fa, s[mid]);
		build(x, ch[x][0], l, mid - 1, s);
		build(x, ch[x][1], mid + 1, r, s);
		C[x] += C[ch[x][0]] + C[ch[x][1]];
	}
	void Move(int &x, int y)
	{
		for (int i = x; i;)
		{
			pushdown(i);
			if (y < C[ch[i][0]]) { i = ch[i][0]; continue; }
			if (y == C[ch[i][0]]) { Splay(i, x); x = i; break; }
			y -= C[ch[i][0]] + 1;	i = ch[i][1];
		}
	}
	void Delete(int &x, int y)
	{
		for (int i = ch[x][1]; i;)
		{
			pushdown(i);
			if (y < C[ch[i][0]]) { i = ch[i][0]; continue; }
			if (y == C[ch[i][0]]) { Splay(i, ch[x][1]); ch[x][1] = i; break; }
			y -= C[ch[i][0]] + 1;	i = ch[i][1];
		}
		int add = C[ch[ch[x][1]][0]];
		ch[ch[x][1]][0] = 0;	C[x] -= add;	C[ch[x][1]] -= add;
	}
	void Rotate(int &x, int y)
	{
		for (int i = ch[x][1]; i;)
		{
			pushdown(i);
			if (y < C[ch[i][0]]) { i = ch[i][0]; continue; }
			if (y == C[ch[i][0]]) { Splay(i, ch[x][1]); ch[x][1] = i; break; }
			y -= C[ch[i][0]] + 1;	i = ch[i][1];
		}
		R[ch[ch[x][1]][0]] ^= 1;
	}
	void Get(int &x)
	{
		for (int i = ch[x][1]; i; i = ch[i][0])
		{
			pushdown(i);
			if (!ch[i][0]) { Splay(i, ch[x][1]); ch[x][1] = i; break; }
		}
		printf("%c\n", S[ch[x][1]]);
	}
	void Prev(int &x)
	{
		for (int i = ch[x][0]; i; i = ch[i][1])
		{
			pushdown(i);
			if (!ch[i][1]) { Splay(i, x); x = i; break; }
		}
	}
	void Next(int &x)
	{
		for (int i = ch[x][1]; i; i = ch[i][0])
		{
			pushdown(i);
			if (!ch[i][0]) { Splay(i, x); x = i; break; }
		}
	}
	void Insert(int &x, int y)
	{
		gets(s);	gets(s);
		int root = 0;
		build(0, root, 0, y - 1, s);
		for (int i = ch[x][1]; i; i = ch[i][0])
		{
			pushdown(i);
			if (!ch[i][0]) { Splay(i, ch[x][1]); ch[x][1] = i; break; }
		}
		ch[ch[x][1]][0] = root;	F[root] = ch[x][1];
		C[x] += C[root];	C[ch[x][1]] += C[root];
	}
}solve;


int main()
{
	cin >> T;
	root = 0;	solve.clear();
	s[0] = s[1] = 0;
	solve.build(0, root, 0, 1, s);
	while (T--)
	{
		scanf("%s", s);
		if (s[0] == 'M') scanf("%d", &x), solve.Move(root, x);
		if (s[0] == 'D') scanf("%d", &x), solve.Delete(root, x);
		if (s[0] == 'R') scanf("%d", &x), solve.Rotate(root, x);
		if (s[0] == 'G') solve.Get(root);
		if (s[0] == 'P') solve.Prev(root);
		if (s[0] == 'N') solve.Next(root);
		if (s[0] == 'I') scanf("%d", &x), solve.Insert(root, x);
	}
	return 0;
}