fork(1) download
copy 
  1. #include <cstdio>
  2. #include <iostream>
  3. #include <string>
  4. #include <algorithm>
  5. #include <cstring>
  6.  
  7. using namespace std;
  8.  
  9. const int N = 100010;
  10.  
  11. struct Node
  12. {
  13.     int letter[26];
  14.     char c;
  15. };
  16.  
  17. Node t[4 * N + 1];
  18. string s;
  19.  
  20. Node join(Node l, Node r)
  21. {
  22.     Node node;
  23.  
  24.     for(int i = 0; i < 26; i++)
  25.     {
  26.         node.letter[i] = l.letter[i] + r.letter[i];
  27.     }
  28.  
  29.     return node;
  30. }
  31.  
  32. void build(int p, int l, int r)
  33. {
  34.     if(l == r)
  35.     {
  36.         t[p].letter[s[l] - 'A'] = 1;
  37.         t[p].c = s[l];
  38.  
  39.         return;
  40.     }
  41.  
  42.     int mid = (l + r) / 2;
  43.  
  44.     build(2 * p, l, mid);
  45.     build(2 * p + 1, mid + 1, r);
  46.  
  47.     t[p] = join(t[2 * p], t[2 * p + 1]);
  48.  
  49. }
  50.  
  51. void update(int p, int l, int r, int i, char c)
  52. {
  53.     char cc = t[p].c;
  54.  
  55.     if(l == r)
  56.     {
  57.         t[p].letter[cc - 'A'] = 0;
  58.         t[p].letter[c - 'A'] = 1;
  59.         t[p].c = c;
  60.         return;
  61.     }
  62.  
  63.     int mid = (l + r) / 2;
  64.  
  65.  
  66.     if(i <= mid)
  67.         update(2 * p, l, mid, i, c);
  68.     else
  69.         update(2 * p + 1, mid + 1, r, i, c);
  70.  
  71.     t[p] = join(t[2 * p], t[2 * p + 1]);
  72. }
  73.  
  74. Node query(int p, int l, int r, int i, int j)
  75. {
  76.     Node node;
  77.     memset(node.letter, 0, sizeof(node.letter));
  78.  
  79.     if(i > r || j < l  || l > r)
  80.         return node;
  81.  
  82.     if(i <= l && r <= j)
  83.         return t[p];
  84.  
  85.     int mid = (l + r) / 2;
  86.  
  87.     Node x, y;
  88.     x = query(2 * p, l, mid, i, j);
  89.     y = query(2 * p + 1, mid + 1, r, i, j);
  90.  
  91.     return join(x, y);
  92. }
  93.  
  94. int main()
  95. {
  96.     int tt, q, l, r;
  97.     char op;
  98.  
  99.     int tc = 1;
  100.  
  101.     scanf("%d", &tt);
  102.  
  103.     while(tt--)
  104.     {
  105.         printf("Case #%d:\n", tc++);
  106.         cin >> s;
  107.         cin >> q;
  108.  
  109.         memset(t, 0, sizeof(t));
  110.         build(1, 0, s.size() - 1);
  111.  
  112.         while(q--)
  113.         {
  114.             cin >> op >> l >> r;
  115.  
  116.             if(op == 's') {
  117.                 sort(s.begin() + l, s.begin() + r + 1);
  118.                 for(int i = l; i <= r; i++)
  119.                     update(1, 0, s.size() - 1, i, s[i]);
  120.             }
  121.             else
  122.             {
  123.                 Node node = query(1, 0, s.size() - 1, l, r);
  124.                 for(int i = 0; i < 26; i++) 
  125.                     printf("%d%c", node.letter[i], (i == 25) ? '\n' : ' ');
  126.             }
  127.         }
  128.     }
  129.  
  130.     return 0;
  131. }
Runtime error #stdin #stdout 0.04s 53600KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/5LMihn
language:
C++14 (gcc 8.3)
created:
10 years 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!