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 = 4000000;
  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. void Reverse(int w)
  81. {
  82. 	rev[w] = !rev[w];
  83. }
  84.  
  85. void Down(int w)
  86. {
  87. 	if (rev[w])
  88. 	{
  89. 		rev[w] = false;
  90. 		int a = l[w];
  91. 		l[w] = r[w];
  92. 		r[w] = a;
  93. 		if (l[w] != 0) Reverse(l[w]);
  94. 		if (r[w] != 0) Reverse(r[w]);
  95. 	}
  96. }
  97.  
  98. int Find(int m)
  99. {
  100. 	int w = l[0];
  101. 	Down(w);
  102. 	while (m != s[l[w]]+1)
  103. 	{
  104. 		if (m < s[l[w]]+1) w = l[w];
  105. 		else
  106. 		{
  107. 			m -= s[l[w]]+1;
  108. 			w = r[w];
  109. 		}
  110. 		Down(w);
  111. 	}
  112. 	return w;
  113. }
  114.  
  115. void RotateL(int w)
  116. {
  117. 	int o = h[w];
  118. 	r[o] = l[w]; h[r[o]] = o;
  119. 	l[w] = o; h[w] = h[o]; 
  120. 	h[o] = w; 
  121. 	if (l[h[w]] == o) l[h[w]] = w; else r[h[w]] = w;
  122. 	Calculate(o);
  123. }
  124.  
  125. void RotateR(int w)
  126. {
  127. 	int o = h[w];
  128. 	l[o] = r[w]; h[l[o]] = o;
  129. 	r[w] = o; h[w] = h[o]; 
  130. 	h[o] = w; 
  131. 	if (l[h[w]] == o) l[h[w]] = w; else r[h[w]] = w;
  132. 	Calculate(o);
  133. }
  134.  
  135. void Splay(int w)
  136. {
  137. 	while (h[w] != 0)
  138. 	{
  139. 		if (l[h[w]] == w) RotateR(w); else RotateL(w);
  140. 	}
  141. 	Calculate(w);
  142. }
  143.  
  144. void FindAll(int b, int e)
  145. {
  146. 	Splay(Find(e));
  147. 	Splay(Find(b));
  148. }
  149.  
  150. int main()
  151. {
  152. 	rep(i, 0, DS-1) n[i] = i+1; last = 0;
  153. 	rep(i, 1, 3) q = NewTree();
  154. 	l[0] = 1; h[1] = 0;
  155. 	r[1] = 2; h[2] = 1;
  156. 	s[1] = 2; s[2] = 1;
  157. 	scanf("%d", &q);
  158. 	w = 1;
  159. 	while (q > 0)
  160. 	{
  161. 		q --;
  162. 		scanf("%s", que);
  163. 		if (que[0] == 'I')
  164. 		{
  165. 			scanf("%d", &m);
  166. 			FindAll(w, w+1);
  167. 			Insert(m);
  168. 		}
  169. 		else if (que[0] == 'M') 
  170. 		{
  171. 			scanf("%d", &w); w ++;
  172. 		}
  173. 		else if (que[0] == 'D')
  174. 		{
  175. 			scanf("%d", &m);
  176. 			FindAll(w, w+m+1);
  177. 			Delete();
  178. 		}
  179. 		else if (que[0] == 'R')
  180. 		{
  181. 			scanf("%d", &m);
  182. 			FindAll(w, w+m+1);
  183. 			Reverse(l[r[l[0]]]);
  184. 			Calculate(r[l[0]]);
  185. 			Calculate(l[0]);
  186. 		}
  187. 		else if (que[0] == 'G') printf("%c\n", key[Find(w+1)]);
  188. 		else if (que[0] == 'P') w --;
  189. 		else if (que[0] == 'N') w ++;
  190. 	}
  191. 	return 0;
  192. }
Success #stdin #stdout 0.01s 93184KB
comments (?)
stdin
copy 
10
Insert 13
Balanced eert
Move 2
Delete 5
Next
Insert 7
 editor
Move 0
Get
Move 11
Rotate 4
Get
stdout
copy 
B
t
https://ideone.com/JoTIfE
BZOJ 1269
language:
C++ (gcc 8.3)
created:
10 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!