fork download
copy 
  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
comments (?)
stdin
copy 
ADAMAAM
2
1 A 2 M
1 A 2 M
stdout
copy 
MDMAAAA
https://ideone.com/KEoAKl
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
secret

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!