fork download
copy 
  1. #include <cstdio>
  2. #include <iostream>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <fstream>
  6.  
  7. #define rep( i, l, r ) for (int i = l; i <= r; i++)
  8. #define down( i, l, r ) for (int i = l; i >= r; i--)
  9.  
  10. const int DS = 5000000;
  11.  
  12. using namespace std;
  13. int h[DS], l[DS], r[DS], n[DS], s[DS];
  14. char key[DS];
  15. bool rev[DS], same[DS];
  16. int q, m, w, last;
  17. char que[50];
  18.  
  19. int NewTree()
  20. {
  21. 	int a = last;
  22. 	last = n[a];
  23. 	h[a] = l[a] = r[a] = n[a] = s[a] = 0;
  24. 	rev[a] = same[a] = false;
  25. 	key[a] = '$';
  26. 	return a;
  27. }
  28.  
  29. void Calculate(int w)
  30. {
  31. 	s[w] = s[l[w]] + 1 + s[r[w]];
  32. }
  33.  
  34. void InsertR(int w)
  35. {
  36. 	int zuo = s[w] / 2;
  37. 	int you = s[w] - zuo - 1;
  38. 	if (zuo > 0)
  39. 	{
  40. 		int a = l[w] = NewTree(); h[a] = w; s[a] = zuo;
  41. 		InsertR(a);
  42. 	}
  43. 	key[w] = getchar();
  44. 	while (key[w] < 32 || key[w] > 126) scanf("%c", &key[w]);
  45. 	if (you > 0)
  46. 	{
  47. 		int a = r[w] = NewTree(); h[a] = w; s[a] = you;
  48. 		InsertR(a);
  49. 	}
  50. 	Calculate(w);
  51. }
  52.  
  53. void Insert(int m)
  54. {
  55. 	int a = l[r[l[0]]] = NewTree();
  56. 	h[a] = r[l[0]];
  57. 	s[a] = m;
  58. 	InsertR(a);
  59. 	Calculate(r[l[0]]);
  60. 	Calculate(l[0]);
  61. }
  62.  
  63. void DeleteR(int w)
  64. {
  65. 	if (l[w] != 0) DeleteR(l[w]);
  66. 	if (r[w] != 0) DeleteR(r[w]);
  67. 	n[w] = last;
  68. 	last = w;
  69. }
  70.  
  71. void Delete()
  72. {
  73. 	int a = l[r[l[0]]];
  74. 	l[r[l[0]]] = 0;
  75. 	DeleteR(a);
  76. 	Calculate(r[l[0]]);
  77. 	Calculate(l[0]);
  78. }
  79.  
  80. int Find(int m)
  81. {
  82. 	int w = l[0];
  83. 	while (m != s[l[w]]+1)
  84. 	{
  85. 		if (m < s[l[w]]+1) w = l[w];
  86. 		else
  87. 		{
  88. 			m -= s[l[w]]+1;
  89. 			w = r[w];
  90. 		}
  91. 	}
  92. 	return w;
  93. }
  94.  
  95. void RotateL(int w)
  96. {
  97. 	int o = h[w];
  98. 	r[o] = l[w]; h[r[o]] = o;
  99. 	l[w] = o; h[w] = h[o]; 
  100. 	h[o] = w; 
  101. 	if (l[h[w]] == o) l[h[w]] = w; else r[h[w]] = w;
  102. 	Calculate(o);
  103. }
  104.  
  105. void RotateR(int w)
  106. {
  107. 	int o = h[w];
  108. 	l[o] = r[w]; h[l[o]] = o;
  109. 	r[w] = o; h[w] = h[o]; 
  110. 	h[o] = w; 
  111. 	if (l[h[w]] == o) l[h[w]] = w; else r[h[w]] = w;
  112. 	Calculate(o);
  113. }
  114.  
  115. void Splay(int w)
  116. {
  117. 	while (h[w] != 0)
  118. 	{
  119. 		if (l[h[w]] == w) RotateR(w); else RotateL(w);
  120. 	}
  121. 	Calculate(w);
  122. }
  123.  
  124. void FindAll(int b, int e)
  125. {
  126. 	Splay(Find(e));
  127. 	Splay(Find(b));
  128. }
  129.  
  130. void Mol(int w)
  131. {
  132. 	if (l[w] != 0) Mol(l[w]);
  133. 	printf("%c", key[w]);
  134. 	if (r[w] != 0) Mol(r[w]);
  135. }
  136.  
  137. int main()
  138. {
  139. 	rep(i, 0, DS-1) n[i] = i+1; last = 0;
  140. 	rep(i, 1, 3) q = NewTree();
  141. 	l[0] = 1; h[1] = 0;
  142. 	r[1] = 2; h[2] = 1;
  143. 	s[1] = 2; s[2] = 1;
  144. 	scanf("%d", &q);
  145. 	w = 1;
  146. 	while (q > 0)
  147. 	{
  148. 		q --;
  149. 		scanf("%s", que);
  150. 		if (que[0] == 'I')
  151. 		{
  152. 			scanf("%d", &m);
  153. 			FindAll(w, w+1);
  154. 			Insert(m);
  155. 		}
  156. 		else if (que[0] == 'M') 
  157. 		{
  158. 			scanf("%d", &w); w ++;
  159. 		}
  160. 		else if (que[0] == 'D')
  161. 		{
  162. 			scanf("%d", &m);
  163. 			FindAll(w, w+m+1);
  164. 			Delete();
  165. 		}
  166. 		else if (que[0] == 'G') 
  167. 		{
  168. 			scanf("%d", &m);
  169. 			FindAll(w, w+m+1);
  170. 			Mol(l[r[l[0]]]);
  171. 			printf("\n");
  172. 		}
  173. 		else if (que[0] == 'P') w --;
  174. 		else if (que[0] == 'N') w ++;
  175. 	}
  176. 	return 0;
  177. }
  178.  
Success #stdin #stdout 0.01s 115648KB
comments (?)
stdin
copy 
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
stdout
copy 
.\/.
abcde^_^f.\/.ghijklmno
https://ideone.com/arVAVC
BZOJ 1507
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!