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 123456
  13. #define MAX 1037471823
  14. #define Q 1
  15.  
  16. using namespace std;
  17.  
  18. int n, m, s[MS], l[MS], r[MS], h[MS], now, k[MS], c, b, e;
  19. bool rev[MS];
  20.  
  21. void New(int o) { s[o] = 1, h[o] = l[o] = r[o] = k[o] = rev[o] = 0; }
  22.  
  23. void Cal(int o) { if (!o) return; s[o] = s[l[o]] + s[r[o]] + 1; }
  24.  
  25. 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; }
  26.  
  27. void Splay(int x)
  28. {
  29. 	if (!x) return; int o = h[x]; Down(x);
  30. 	while (o)
  31. 	{
  32. 		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; r[x] = o, h[o] = x; Cal(o); }
  33. 		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; l[x] = o, h[o] = x; Cal(o); }
  34. 		o = h[x];
  35. 	}
  36. 	Cal(x);
  37. }
  38.  
  39. void Insert(int o, int n)
  40. {
  41. 	int ln = (n-1) / 2, rn = n-ln-1;
  42. 	if (ln) { New(++now); h[now] = o, l[o] = now; Insert(now, ln); }
  43. 	k[o] = ++c;
  44. 	if (rn) { New(++now); h[now] = o, r[o] = now; Insert(now, rn); }
  45. 	Cal(o);
  46. }
  47.  
  48. void PrintP(int o) { Down(o); if (l[o]) PrintP(l[o]); if (!c) printf("%d", k[o]); else printf(" %d", k[o]); c++; if (r[o]) PrintP(r[o]); }
  49.  
  50. int FindRW(int rr) { int o = l[0]; Down(o); while (rr != s[l[o]]) { if (rr < s[l[o]]) o = l[o]; else rr -= s[l[o]] + 1, o = r[o]; Down(o); } return o; }
  51.  
  52. 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); }
  53.  
  54. void Print(int b, int n) { Splay(FindRW(b-1)); Splay(FindRW(b+n)); PrintP(r[l[l[0]]]); }
  55.  
  56. int main()
  57. {
  58. 	scanf("%d%d", &n, &m);
  59. 	s[1] = s[2] = s[3] = 1; l[0] = 1, l[1] = 2, h[2] = 1, r[2] = 3, h[3] = 2; now = 3;
  60. 	Insert(3, n); Cal(2); Cal(1);
  61. 	rep(i, 1, m) 
  62. 	{
  63. 		scanf("%d%d", &b, &e);
  64. 		Rev(b, e-b+1);
  65. 	}
  66. 	c = 0; Print(1, n); 
  67. 	return 0;
  68. }
Success #stdin #stdout 0s 5832KB
comments (?)
stdin
copy 
5 3
1 3
1 3
1 4
stdout
copy 
4 3 2 1 5
https://ideone.com/Ql0Egm
BZOJ 3223
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!