Advertisement
Guest User

Untitled

a guest
Apr 21st, 2019
86
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.78 KB | None | 0 0
  1. // Solution By Chynti :)
  2. #include <bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6. const int N = 3e5+10;
  7.  
  8. typedef struct Treap* treap;
  9.  
  10. struct Treap {
  11. int x, y, cnt;
  12. treap l, r;
  13. Treap(int _x) {
  14. cnt = 1, x = _x, y = rand();
  15. l = r = NULL;
  16. }
  17. };
  18.  
  19. int cnt(treap t) {
  20. return t ? t->cnt : 0;
  21. }
  22.  
  23. void upd_cnt(treap t) {
  24. if (t)
  25. t->cnt = cnt(t->l) + cnt(t->r) + 1;
  26. }
  27.  
  28.  
  29. void spl(treap t, treap &l, treap &r, int x, int add = 1) {
  30. if (!t)
  31. return void(l = r = NULL);
  32. int cur_x = add + cnt(t->l);
  33. if (cur_x < x)
  34. spl(t->r, t->r, r, x, cur_x + 1), l = t;
  35. else
  36. spl(t->l, l, t->l, x, add), r = t;
  37. upd_cnt(l);
  38. upd_cnt(r);
  39. upd_cnt(t);
  40. }
  41.  
  42.  
  43. void mer(treap &t, treap l, treap r) {
  44. if (!l || !r)
  45. t = l ? l : r;
  46. else if (l->y > r->y)
  47. mer(l->r, l->r, r), t = l;
  48. else
  49. mer(r->l, l, r->l), t = r;
  50. upd_cnt(t);
  51. }
  52.  
  53. treap t;
  54.  
  55. int n, m;
  56. int p[N], a[N];
  57. vector <int> res;
  58.  
  59. int find_set(int a) {
  60. if (p[a] == a)
  61. return a;
  62. return p[a] = find_set(p[a]);
  63. }
  64.  
  65. void prin(treap t) {
  66. if (!t) return;
  67. prin(t->l);
  68. res.push_back(t->x);
  69. if (t->x) n--;
  70. if (!n) {
  71. cout << res.size() << endl;
  72. for (int i = 0; i < res.size(); i++)
  73. cout << res[i] << " ";
  74. exit(0);
  75. }
  76. prin(t->r);
  77. }
  78.  
  79. int main() {
  80. scanf("%d%d", &n, &m);
  81. for (int i = 1; i <= 300000; i++) {
  82. p[i] = i;
  83. mer(t, t, new Treap(0));
  84. }
  85.  
  86. for (int i = 1, x; i <= n; i++) {
  87. scanf("%d", &x);
  88. treap a, b, c, d;
  89. spl(t, a, b, x);
  90. spl(b, b, c, find_set(x)+1 - cnt(a));
  91. spl(b, b, d, find_set(x) - cnt(a));
  92. mer(b, b, c);
  93. mer(b, new Treap(i), b);
  94. mer(t, a, b);
  95. p[find_set(x)] = find_set(x) + 1;
  96. }
  97. prin(t);
  98. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement