fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. string s;
  5. vector<vector<int>> tree;
  6.  
  7. void init_tree(int tree_id, int node_id = 1, int left = 0, int right = s.size())
  8. {
  9. if (left + 1 == right) {
  10. tree[tree_id][node_id] = (s[left] - 'A') == tree_id;
  11. return;
  12. }
  13. int middle = (left + right) / 2;
  14. init_tree(tree_id, node_id + node_id, left, middle);
  15. init_tree(tree_id, node_id + node_id + 1, middle, right);
  16. tree[tree_id][node_id] = tree[tree_id][node_id + node_id] + tree[tree_id][node_id + node_id + 1];
  17. }
  18.  
  19. void update_tree(int tree_id, int position, int value, int node_id = 1, int left = 0, int right = s.size())
  20. {
  21. if (position < left || right <= position) {
  22. return;
  23. }
  24. if (left + 1 == right) {
  25. tree[tree_id][node_id] += value;
  26. return;
  27. }
  28. int middle = (left + right) / 2;
  29. update_tree(tree_id, position, value, node_id + node_id, left, middle);
  30. update_tree(tree_id, position, value, node_id + node_id + 1, middle, right);
  31. tree[tree_id][node_id] = tree[tree_id][node_id + node_id] + tree[tree_id][node_id + node_id + 1];
  32. }
  33.  
  34. int query_tree(int tree_id, int number, int node_id = 1, int left = 0, int right = s.size())
  35. {
  36. if (left + 1 == right) {
  37. return left;
  38. }
  39. int middle = (left + right) / 2;
  40. if (number <= tree[tree_id][node_id + node_id]) {
  41. return query_tree(tree_id, number, node_id + node_id, left, middle);
  42. } else {
  43. return query_tree(tree_id, number - tree[tree_id][node_id + node_id], node_id + node_id + 1, middle, right);
  44. }
  45. }
  46.  
  47. void save_tree_to_string(int tree_id, int node_id = 1, int left = 0, int right = s.size())
  48. {
  49. if (tree[tree_id][node_id] == 0) {
  50. return;
  51. }
  52. if (left + 1 == right) {
  53. if (tree[tree_id][node_id] == 1) {
  54. s[left] = (char)('A' + tree_id);
  55. }
  56. return;
  57. }
  58. int middle = (left + right) / 2;
  59. save_tree_to_string(tree_id, node_id + node_id, left, middle);
  60. save_tree_to_string(tree_id, node_id + node_id + 1, middle, right);
  61. }
  62.  
  63. int main()
  64. {
  65. int q;
  66. cin >> s >> q;
  67. tree.assign(26, vector<int>(4 * s.size(), 0));
  68. for (int i = 0; i < 26; ++i) {
  69. init_tree(i);
  70. }
  71. while (q--) {
  72. int number_1, number_2;
  73. char letter_1, letter_2;
  74. cin >> number_1 >> letter_1 >> number_2 >> letter_2;
  75. int position_1 = query_tree(letter_1 - 'A', number_1);
  76. int position_2 = query_tree(letter_2 - 'A', number_2);
  77. update_tree(letter_1 - 'A', position_1, -1);
  78. update_tree(letter_1 - 'A', position_2, 1);
  79. update_tree(letter_2 - 'A', position_2, -1);
  80. update_tree(letter_2 - 'A', position_1, 1);
  81. }
  82. for (int i = 0; i < 26; ++i) {
  83. save_tree_to_string(i);
  84. }
  85. cout << s << endl;
  86. return 0;
  87. }
Success #stdin #stdout 0s 4284KB
stdin
ADAMAAM
2
1 A 2 M
1 A 2 M
stdout
MDMAAAA