fork download
  1. #include <stdio.h>
  2. #include <vector>
  3. #include <iostream>
  4.  
  5. using namespace std;
  6.  
  7. struct node {
  8. int sum;
  9. node *left, *right;
  10.  
  11. node(int low, int high)
  12. {
  13. sum = (high - low + 1);
  14. left = NULL;
  15. right = NULL;
  16. }
  17.  
  18. void extend(int l, int r)
  19. {
  20. if (left == NULL) {
  21. int mid = (l + r) >> 1;
  22. left = new node(l, mid);
  23. right = new node(mid + 1, r);
  24. }
  25. }
  26. };
  27.  
  28. node* Root;
  29.  
  30. void updateSegTree(int index, int delta, node* root, int l, int r)
  31. {
  32. if (index < l || index > r)
  33. return;
  34.  
  35. if (l == r) {
  36. root->sum += delta;
  37. return;
  38. }
  39.  
  40. root->extend(l, r);
  41. updateSegTree(index, delta, root->left, l, (l+r) / 2);
  42. updateSegTree(index, delta, root->right, (l+r) / 2 + 1, r);
  43. root->sum = (root->left)->sum + (root->right)->sum;
  44. }
  45.  
  46. int query(int k, node* root, int l, int r)
  47. {
  48. if (l == r)
  49. return l;
  50.  
  51. root->extend(l, r);
  52. if ((root->left)->sum >= k)
  53. return query(k, root->left, l, (l+r)/2);
  54. return query(k - ((root->left)->sum), root->right, (l+r)/2+1, r);
  55. }
  56.  
  57. int main()
  58. {
  59. //std::cerr << sizeof(node) << std::endl;
  60. int n, m, num;
  61. char op;
  62.  
  63. scanf("%d%d", &n, &m);
  64.  
  65. Root = new node(1, n);
  66.  
  67. for (int i = 1; i <= m; i++) {
  68. scanf(" %c %d", &op, &num);
  69. int q = query(num, Root, 1, n);
  70. if (op == 'L')
  71. printf("%d\n", q);
  72. else
  73. updateSegTree(q, -1, Root, 1, n);
  74. }
  75. return 0;
  76. }
Success #stdin #stdout 0s 4568KB
stdin
20 7
L 5
D 5
L 4
L 5
D 5
L 4
L 5
stdout
5
4
6
4
7