Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // #### Zeinab
- #include<bits/stdc++.h>
- using namespace std;
- #define nl "\n"
- #define fi first
- #define se second
- #define pb push_back
- #define ll long long
- #define RV return void
- #define sz(x) int(x.size())
- #define all(v) v.begin(), v.end()
- #define rall(v) v.rbegin(), v.rend()
- #define cin(v) for(auto&x:v) cin >> x;
- #define cout(v) for(auto&x:v) cout << x << " ";
- string s;
- struct Node{
- vector < int > freq;
- Node(){
- freq = vector < int > (26,0);
- }
- Node(int idx ,char c){
- freq[s[idx]-'a']--;
- freq[c-'a']++;
- s[idx]=c;
- }
- };
- struct SegTree{
- int tree_size;
- vector<Node> tree;
- SegTree(int n){
- tree_size = 1;
- while (tree_size < n) tree_size *= 2;
- tree.assign(2 * tree_size, Node());
- }
- Node merge(Node &left, Node &right){
- Node ans = Node();
- for(int i =0 ; i < 26 ; i++){
- ans.freq[i] = left.freq[i] + right.freq[i];
- }
- return ans;
- }
- void build(string & s, int node, int lx, int rx){
- if(rx - lx == 1){
- if(lx < sz(s) )
- tree[node]= Node(lx , s[lx]);
- return;
- }
- int md = lx + (rx - lx) / 2;
- build(s, 2 * node + 1, lx, md);
- build(s, 2 * node + 2, md, rx);
- tree[node] = merge(tree[2 * node + 1], tree[2 * node + 2]);
- }
- void build(string & s){
- build(s, 0, 0, tree_size);
- }
- void set(int idx, char val, int node, int lx, int rx){
- if(rx - lx == 1){
- tree[node] = Node(idx , val);
- return;
- }
- int md = lx + (rx - lx) / 2;
- if(idx < md)
- set(idx, val, 2 * node + 1, lx, md);
- else
- set(idx, val, 2 * node + 2, md, rx);
- tree[node] = merge(tree[2 * node + 1], tree[2 * node + 2]);
- }
- void set(int idx, char val){
- set(idx, val, 0, 0, tree_size);
- }
- Node get(int l, int r, ll node, int lx, int rx){
- if(lx >= l and rx <= r)
- return tree[node];
- if(lx >= r or rx <= l)
- return Node();
- int md = lx + (rx - lx) / 2;
- Node left = get(l, r, 2 * node + 1, lx, md);
- Node right = get(l, r, 2 * node + 2, md, rx);
- return merge(left, right);
- }
- Node get(int l, int r){
- // call from l to r+1 in main
- return get(l, r, 0, 0, tree_size);
- }
- };
- void solve(){
- int n , q , l , r , idx , op ;
- char val;
- cin >> s >> q;
- n = sz(s);
- SegTree seg(n);
- seg.build(s);
- while(q--){
- cin >> op;
- if(op == 1){
- cin >> idx >> val;
- seg.set(idx-1 , val);
- }else{
- cin >> l >> r;
- l--;
- auto vec = seg.get(l,r).freq;
- idx=0;
- for(int i =0 ; i < 26 ; i++){
- idx += (vec[i]>0);
- }
- cout << idx << nl;
- }
- }
- }
- int main(){
- ios_base::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
- int t=1;
- // cin >> t ;
- for(int i=1 ; i <= t ; i++){
- // cout << "Case #"<< i <<": ";
- solve();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement