fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4.  
  5. using namespace std;
  6.  
  7. const int MAXN = 1000005;
  8.  
  9. struct Node {
  10.     int cnt[5];
  11.     char map[5];
  12. } tree[4 * MAXN];
  13.  
  14. int n, m;
  15. string initial_str;
  16.  
  17. void push_up(int node) {
  18.     for (int i = 0; i < 5; ++i) {
  19.         tree[node].cnt[i] = tree[2 * node].cnt[i] + tree[2 * node + 1].cnt[i];
  20.     }
  21. }
  22.  
  23. void apply_map(int node, const char* p_map) {
  24.     int new_cnt[5] = {0};
  25.     char new_map[5];
  26.  
  27.     for (int i = 0; i < 5; ++i) {
  28.         new_cnt[p_map[i]] += tree[node].cnt[i];
  29.         new_map[i] = p_map[tree[node].map[i]];
  30.     }
  31.  
  32.     for (int i = 0; i < 5; ++i) {
  33.         tree[node].cnt[i] = new_cnt[i];
  34.         tree[node].map[i] = new_map[i];
  35.     }
  36. }
  37.  
  38. void push_down(int node) {
  39.     apply_map(2 * node, tree[node].map);
  40.     apply_map(2 * node + 1, tree[node].map);
  41.     for (int i = 0; i < 5; ++i) tree[node].map[i] = i;
  42. }
  43.  
  44. void build(int node, int start, int end) {
  45.     for (int i = 0; i < 5; ++i) tree[node].map[i] = i;
  46.  
  47.     if (start == end) {
  48.         tree[node].cnt[initial_str[start - 1] - 'a'] = 1;
  49.         return;
  50.     }
  51.  
  52.     int mid = (start + end) / 2;
  53.     build(2 * node, start, mid);
  54.     build(2 * node + 1, mid + 1, end);
  55.     push_up(node);
  56. }
  57.  
  58. int find_kth(int node, int start, int end, int k, int color) {
  59.     if (start == end) return start;
  60.  
  61.     push_down(node);
  62.     int mid = (start + end) / 2;
  63.     int left_count = tree[2 * node].cnt[color];
  64.  
  65.     if (k <= left_count) {
  66.         return find_kth(2 * node, start, mid, k, color);
  67.     } else {
  68.         return find_kth(2 * node + 1, mid + 1, end, k - left_count, color);
  69.     }
  70. }
  71.  
  72. void update(int node, int start, int end, int l, int r, int c_from, int c_to) {
  73.     if (l > end || r < start) return;
  74.  
  75.     if (l <= start && end <= r) {
  76.         char trans[5];
  77.         for(int i = 0; i < 5; ++i) trans[i] = i;
  78.         trans[c_from] = c_to;
  79.         apply_map(node, trans);
  80.         return;
  81.     }
  82.  
  83.     push_down(node);
  84.     int mid = (start + end) / 2;
  85.     update(2 * node, start, mid, l, r, c_from, c_to);
  86.     update(2 * node + 1, mid + 1, end, l, r, c_from, c_to);
  87.     push_up(node);
  88. }
  89.  
  90. void print_tree(int node, int start, int end) {
  91.     if (start == end) {
  92.         for (int i = 0; i < 5; ++i) {
  93.             if (tree[node].cnt[i]) {
  94.                 cout << (char)('a' + i);
  95.                 return;
  96.             }
  97.         }
  98.         return;
  99.     }
  100.  
  101.     push_down(node);
  102.     int mid = (start + end) / 2;
  103.     print_tree(2 * node, start, mid);
  104.     print_tree(2 * node + 1, mid + 1, end);
  105. }
  106.  
  107. int main() {
  108.     ios_base::sync_with_stdio(false);
  109.     cin.tie(NULL);
  110.  
  111.     cin >> n >> m >> initial_str;
  112.  
  113.     build(1, 1, n);
  114.  
  115.     for (int i = 0; i < m; ++i) {
  116.         int p;
  117.         char c1, c2;
  118.         cin >> p >> c1 >> c2;
  119.         int color_from = c1 - 'a';
  120.         int color_to = c2 - 'a';
  121.  
  122.         if (color_from == color_to || p == 0) continue;
  123.  
  124.         int idx = find_kth(1, 1, n, p, color_from);
  125.         update(1, 1, n, 1, idx, color_from, color_to);
  126.     }
  127.  
  128.     print_tree(1, 1, n);
  129.     cout << endl;
  130.  
  131.     return 0;
  132. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
10 3
acabbabbac
3 b c
4 a b
3 c a
stdout
copy 
babaabcbbc
https://ideone.com/jGnJHA
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

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!