fork download
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4.  
  5. #define MAXN (1 << 20)
  6.  
  7. using namespace std;
  8. using namespace __gnu_pbds;
  9.  
  10. template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  11.  
  12. struct node
  13. {
  14. long long cnt;
  15. long long left, right, id;
  16.  
  17. node() {left = -1, right = -1, id = -1; cnt = 0;}
  18. };
  19.  
  20. node broken;
  21.  
  22. struct dynamic_segment_tree
  23. {
  24. long long cnt;
  25. node tr[MAXN];
  26.  
  27. long long newnode()
  28. {
  29. tr[cnt].id = cnt;
  30. return cnt++;
  31. }
  32.  
  33. void expand(long long idx, long long lb, long long rb)
  34. {
  35. long long mid = (lb + rb) >> 1;
  36.  
  37. if(tr[idx].left == -1)
  38. {
  39. tr[idx].left = newnode();
  40. tr[tr[idx].left].cnt = (mid - lb + 1);
  41. }
  42.  
  43. if(tr[idx].right == -1)
  44. {
  45. tr[idx].right = newnode();
  46. tr[tr[idx].right].cnt = (rb - mid);
  47. }
  48. }
  49.  
  50. void init()
  51. {
  52. cnt = 0;
  53. tr[0].id = newnode();
  54. }
  55.  
  56. node merge(node l, node r)
  57. {
  58. node ret;
  59. ret.cnt = l.cnt + r.cnt;
  60. return ret;
  61. }
  62.  
  63. void update(long long idx)
  64. {
  65. tr[idx].cnt = tr[tr[idx].left].cnt + tr[tr[idx].right].cnt;
  66. }
  67.  
  68. long long query(long long k, long long l, long long r, long long idx)
  69. {
  70. if(l == r)
  71. return l;
  72.  
  73. long long mid = (l + r) >> 1;
  74. expand(idx, l, r);
  75.  
  76. //printf("[%lld, %lld] : %lld, --> %lld, %lld\n", l, r, k, tr[tr[idx].left].cnt,
  77. //tr[tr[idx].right].cnt);
  78.  
  79. if(tr[tr[idx].left].cnt >= k) return query(k, l, mid, tr[idx].left);
  80. else return query(k - tr[tr[idx].left].cnt, mid + 1, r, tr[idx].right);
  81. }
  82.  
  83. void update(long long pos, long long val, long long l, long long r, long long idx)
  84. {
  85. if(l > pos || r < pos)
  86. return;
  87.  
  88. if(l == r && l == pos)
  89. {
  90. tr[idx].cnt += val;
  91. return;
  92. }
  93.  
  94. long long mid = (l + r) >> 1;
  95. expand(idx, l, r);
  96.  
  97. //printf("[%lld, %lld] : %lld, --> %lld, %lld\n", l, r, idx, tr[tr[idx].left].cnt,
  98. //tr[tr[idx].right].cnt);
  99.  
  100. update(pos, val, l, mid, tr[idx].left);
  101. update(pos, val, mid + 1, r, tr[idx].right);
  102.  
  103. update(idx);
  104. }
  105. };
  106.  
  107. long long N;
  108.  
  109. void read()
  110. {
  111. scanf("%lld", &N);
  112. }
  113.  
  114. dynamic_segment_tree t;
  115.  
  116. void solve()
  117. {
  118. t.init();
  119.  
  120. long long Q;
  121. scanf("%lld", &Q);
  122.  
  123. while(Q--)
  124. {
  125. char type[2];
  126. long long pos;
  127.  
  128. scanf("%s %lld", &type, &pos);
  129.  
  130. long long val = t.query(pos, 1, N, 0);
  131.  
  132. if(type[0] == 'D')
  133. t.update(val, -1, 1, N, 0);
  134. else
  135. printf("%lld\n", val);
  136. }
  137. }
  138.  
  139. int main()
  140. {
  141. read();
  142. solve();
  143. return 0;
  144. }
  145.  
  146.  
Time limit exceeded #stdin #stdout 5s 36256KB
stdin
Standard input is empty
stdout
Standard output is empty