Advertisement
Zeinab_Hamdy

Untitled

Oct 21st, 2024
92
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.26 KB | None | 0 0
  1. //  #### Zeinab
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. #define nl "\n"
  5. #define fi first
  6. #define se second
  7. #define pb push_back
  8. #define ll long long
  9. #define RV return void
  10. #define sz(x) int(x.size())
  11. #define all(v) v.begin(), v.end()
  12. #define rall(v) v.rbegin(), v.rend()
  13. #define cin(v) for(auto&x:v) cin >> x;
  14. #define cout(v) for(auto&x:v) cout << x << " ";
  15.  
  16. string s;
  17.  
  18. struct Node{
  19.     vector < int > freq;
  20.  
  21.     Node(){
  22.         freq = vector < int > (26,0);
  23.     }
  24.  
  25.     Node(int idx ,char c){
  26.         freq[s[idx]-'a']--;
  27.         freq[c-'a']++;
  28.         s[idx]=c;
  29.     }
  30. };
  31.  
  32. struct SegTree{
  33.     int tree_size;
  34.     vector<Node> tree;
  35.  
  36.  
  37.     SegTree(int n){
  38.         tree_size = 1;
  39.         while (tree_size < n) tree_size *= 2;
  40.         tree.assign(2 * tree_size, Node());
  41.     }
  42.  
  43.  
  44.     Node merge(Node &left, Node &right){
  45.         Node ans = Node();
  46.         for(int i =0 ; i < 26 ; i++){
  47.             ans.freq[i] = left.freq[i] + right.freq[i];
  48.         }
  49.         return ans;
  50.     }
  51.  
  52.  
  53.     void build(string & s, int node, int lx, int rx){
  54.         if(rx - lx == 1){
  55.             if(lx < sz(s) )
  56.                 tree[node]= Node(lx , s[lx]);
  57.             return;
  58.         }
  59.         int md = lx + (rx - lx) / 2;
  60.  
  61.         build(s, 2 * node + 1, lx, md);
  62.         build(s, 2 * node + 2, md, rx);
  63.  
  64.         tree[node] = merge(tree[2 * node + 1], tree[2 * node + 2]);
  65.     }
  66.  
  67.  
  68.     void build(string & s){
  69.         build(s, 0, 0, tree_size);
  70.     }
  71.  
  72.  
  73.     void set(int idx, char val, int node, int lx, int rx){
  74.         if(rx - lx == 1){
  75.             tree[node] = Node(idx , val);
  76.             return;
  77.         }
  78.         int md = lx + (rx - lx) / 2;
  79.  
  80.         if(idx < md)
  81.             set(idx, val, 2 * node + 1, lx, md);
  82.         else
  83.             set(idx, val, 2 * node + 2, md, rx);
  84.  
  85.         tree[node] = merge(tree[2 * node + 1], tree[2 * node + 2]);
  86.     }
  87.  
  88.  
  89.     void set(int idx, char val){
  90.         set(idx, val, 0, 0, tree_size);
  91.     }
  92.  
  93.  
  94.     Node get(int l, int r, ll node, int lx, int rx){
  95.         if(lx >= l and rx <= r)
  96.             return tree[node];
  97.         if(lx >= r or rx <= l)
  98.             return Node();
  99.  
  100.         int md = lx + (rx - lx) / 2;
  101.  
  102.         Node left = get(l, r, 2 * node + 1, lx, md);
  103.         Node right = get(l, r, 2 * node + 2, md, rx);
  104.  
  105.         return merge(left, right);
  106.     }
  107.  
  108.  
  109.     Node get(int l, int r){
  110.         //  call from l to r+1 in main
  111.         return get(l, r, 0, 0, tree_size);
  112.     }
  113. };
  114.  
  115.  
  116. void solve(){
  117.  
  118.     int n , q , l , r , idx , op ;
  119.     char val;
  120.  
  121.     cin >> s >> q;
  122.     n = sz(s);
  123.     SegTree seg(n);
  124.     seg.build(s);
  125.  
  126.     while(q--){
  127.         cin >> op;
  128.         if(op == 1){
  129.             cin >> idx >> val;
  130.             seg.set(idx-1 , val);
  131.         }else{
  132.             cin >> l >> r;
  133.             l--;
  134.             auto vec = seg.get(l,r).freq;
  135.             idx=0;
  136.             for(int i =0 ; i < 26 ; i++){
  137.                 idx += (vec[i]>0);
  138.             }
  139.             cout << idx << nl;
  140.         }
  141.     }
  142.  
  143.  
  144. }
  145.  
  146.  
  147. int main(){
  148.     ios_base::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);  
  149.    
  150.     int t=1;
  151.         // cin >> t ;
  152.     for(int i=1 ; i <= t ; i++){
  153.         // cout << "Case #"<< i <<": ";
  154.         solve();
  155.     }
  156.     return 0;
  157. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement