fork download
copy 
  1. #include <cstring>
  2. #include <cmath>
  3. #include <cstdlib>
  4. #include <algorithm>
  5. #include <fstream>
  6. #include <iostream>
  7. #include <cstdio>
  8. #include <queue>
  9.  
  10. #define rep(i, l, r) for(int i = l; i <= r; i++)
  11. #define down(i, l, r) for(int i = l; i >= r; i--)
  12. #define MS 2345678
  13. #define MAX 1037471823
  14. #define Q 1
  15.  
  16. using namespace std;
  17.  
  18. int m, a, b, n, s[MS], h[MS], l[MS], r[MS], next[MS], last, now;
  19. bool rev[MS];
  20. char c[MS], q[10];
  21.  
  22. int New() { int o = last; last = next[o]; s[o] = 1, h[o] = l[o] = r[o] = c[o] = rev[o] = 0; return o; }
  23.  
  24. void Cal(int o) { if (!o) return; s[o] = s[l[o]]+s[r[o]]+1; }
  25.  
  26. void Down(int o) { if (!o) return; int x; if (rev[o]) x = l[o], l[o] = r[o], r[o] = x, rev[o] ^= 1, rev[l[o]] ^= 1, rev[r[o]] ^= 1; }
  27.  
  28. void Splay(int x)
  29. {
  30. 	if (!x) return; int o = h[x]; Down(x);
  31. 	while (o)
  32. 	{
  33. 		if (l[o] == x) { l[h[o]] == o ? l[h[o]] = x : r[h[o]] = x; h[x] = h[o]; l[o] = r[x]; h[r[x]] = o; h[o] = x; r[x] = o; Cal(o); }
  34. 		else { l[h[o]] == o ? l[h[o]] = x : r[h[o]] = x; h[x] = h[o]; r[o] = l[x]; h[l[x]] = o; h[o] = x; l[x] = o; Cal(o); }
  35. 		o = h[x];
  36. 	}
  37. 	Cal(x);
  38. }
  39.  
  40. int FindRW(int rr) 
  41. { 
  42. 	int o = l[0]; Down(o);
  43. 	while (rr != s[l[o]]) 
  44. 	{
  45. 		if (rr < s[l[o]]) o = l[o]; else rr -= s[l[o]]+1, o = r[o]; 
  46. 		Down(o); 
  47. 	}
  48. 	return o;
  49. }
  50.  
  51. void InsertP(int o, int n) 
  52. {
  53. 	int ln = (n-1) / 2, rn = n - ln - 1;
  54. 	if (ln) { int now = New(); h[now] = o, l[o] = now; InsertP(now, ln); }
  55. 	c[o] = 0; while (c[o] < 32 || 126 < c[o]) scanf("%c", &c[o]);
  56. 	if (rn) { int now = New(); h[now] = o, r[o] = now; InsertP(now, rn); }
  57. 	Cal(o);
  58. }
  59.  
  60. void Insert(int b, int n) { Splay(FindRW(b)); Splay(FindRW(b+1)); int o = New(); h[o] = l[l[0]]; r[l[l[0]]] = o; InsertP(o, n); Cal(l[l[0]]); Cal(l[0]); }
  61.  
  62. void DeleteP(int o) { if (l[o]) DeleteP(l[o]); if (r[o]) DeleteP(r[o]); next[o] = last, last = o; }
  63.  
  64. void Delete(int b, int n) { Splay(FindRW(b-1)); Splay(FindRW(b+n)); DeleteP(r[l[l[0]]]); r[l[l[0]]] = 0; Cal(l[l[0]]); Cal(l[0]); }
  65.  
  66. void Rev(int b, int n) { Splay(FindRW(b-1)); Splay(FindRW(b+n)); int o = r[l[l[0]]]; rev[o] ^= 1; Splay(o); }
  67.  
  68. int main()
  69. {
  70. 	s[1] = 2, s[2] = 1; l[0] = 1, l[1] = 2, h[2] = 1; rep(i, 3, MS-1) next[i] = i+1; last = 3; now = 0;
  71. 	scanf("%d", &m);
  72. 	rep(i, 1, m)
  73. 	{
  74. 		scanf("%s", q);
  75. 		if (q[0] == 'M') scanf("%d", &now);
  76. 		else if (q[0] == 'I') { scanf("%d", &n); Insert(now, n); }
  77. 		else if (q[0] == 'D') { scanf("%d", &n); Delete(now+1, n); }
  78. 		else if (q[0] == 'R') { scanf("%d", &n); Rev(now+1, n); }
  79. 		else if (q[0] == 'G') printf("%c\n", c[FindRW(now+1)]);
  80. 		else if (q[0] == 'P') now--; else now++;
  81. 	}
  82. 	return 0;
  83. }
Success #stdin #stdout 0s 53696KB
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/p1PBEW
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!