Advertisement
Josif_tepe

Untitled

Mar 17th, 2024
656
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.73 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <map>
  4. #include <set>
  5. using namespace std;
  6. const int maxn = 100001;
  7. string s;
  8.  
  9. vector<int> segment_tree[3 * maxn];
  10. void build(int L, int R, int node) {
  11.     if(L == R) {
  12.         cout << L << " " << node<< endl;
  13.         segment_tree[node][s[L] - 'a']++;
  14.         return;
  15.     }
  16.     int mid = (L + R) / 2;
  17.     build(L, mid, 2 * node);
  18.     build(mid + 1, R, 2 * node + 1);
  19.    
  20.     for(int i = 0; i < 26; i++) {
  21.         segment_tree[node][i] = segment_tree[2 * node][i] + segment_tree[2 * node + 1][i];
  22.     }
  23. }
  24. vector<int> my_merge(vector<int> a, vector<int> b) {
  25.     vector<int> c(26, 0);
  26.     for(int i = 0; i < 26; i++) {
  27.         c[i] = a[i] + b[i];
  28.     }
  29.     return c;
  30. }
  31. vector<int> query(int L, int R, int node, int i, int j) {
  32.     // L R i L R j L R
  33.     if(i <= L and R <= j) {
  34.         return segment_tree[node];
  35.     }
  36.     if(R < i or j < L) {
  37.         return vector<int>(26, 0);
  38.     }
  39.     int mid = (L + R) / 2;
  40.     return my_merge(query(L, mid, 2 * node, i, j), query(mid + 1, R, 2 * node + 1, i, j));
  41. }
  42. void update(int L, int R, int node, int idx, char c_val, char n_val) {
  43.     if(L == R) {
  44.         segment_tree[node][c_val - 'a']--;
  45.         segment_tree[node][n_val - 'a']++;
  46.         return;
  47.     }
  48.     int mid = (L + R) / 2;
  49.     if(idx <= mid) {
  50.         update(L, mid, 2 * node, idx, c_val, n_val);
  51.     }
  52.     else {
  53.         update(mid + 1, R, 2 * node + 1, idx, c_val, n_val);
  54.     }
  55.     for(int i = 0; i < 26; i++) {
  56.         segment_tree[node][i] = segment_tree[2 * node][i] + segment_tree[2 * node + 1][i];
  57.     }
  58. }
  59. int main() {
  60.     for(int i = 0; i < 3 * maxn; i++) {
  61.         segment_tree[i] = vector<int>(26, 0);
  62.     }
  63.     cin >> s;
  64.     int n = (int) s.size();
  65.  
  66.     build(0, n - 1, 1);
  67.    
  68.     int q;
  69.     cin >> q;
  70.    
  71.     while(q--) {
  72.         int type;
  73.         cin >> type;
  74.        
  75.         if(type == 2) {
  76.             int L, R;
  77.             cin >> L >> R;
  78.             string tmp;
  79.             cin >> tmp;
  80.            
  81.             vector<int> freq = query(0, n - 1, 1, L, R);
  82.             long long res = 1;
  83.             for(int i =0 ; i < 26; i++) {
  84.                 if(freq[i] > 0) {
  85.                     cout << (char) (i + 'a') << " " << freq[i] << endl;
  86.                 }
  87.             }
  88.             for(int i = 0; i < tmp.size(); i++) {
  89.                 res *= freq[tmp[i] - 'a'];
  90.                 res %= 1000000007;
  91.             }
  92.             cout << res << endl;
  93.         }
  94.         else {
  95.             int idx;
  96.             char c;
  97.             cin >> idx >> c;
  98.             update(0, n - 1, 1, idx, s[idx], c);
  99.             s[idx] = c;
  100.         }
  101.     }
  102.    
  103.     return 0;
  104. }
  105. // gxeekkksgskeegks
  106. // 1 7 gek
  107. /*
  108. geeekkksgskeegks
  109. 3
  110. 2 0 6 gek
  111. */
  112.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement