power of three

/*
Power of 3

Problem Description

Given a binary string A of size N and an integer matrix B of size Q x 3.

Matrix B has Q queries:

    For queries of type B[i][0] = 1, flip the value at index B[i][1] in A if and only if the value at that index is 0 and return -1.
    For queries of type B[i][0] = 0, Return the value of the binary string from index B[i][1] to B[i][2] modulo 3.

    Note: Rows are numbered from top to bottom and columns are numbered from left to right.



Problem Constraints

1 <= N <= 100000
1 <= Q <= 200000
1 <= B[i][1], B[i][2] <= N
B[i][1] <= B[i][2]


Input Format

The first argument given is the string A.
The second argument given is the integer matrix B of size Q * 3.


Output Format

Return an array of size Q where ith value is answer to ith query.


Example Input

Input 1:

 A = 10010
 B = [  [0, 3, 5]
        [0, 3, 4]
        [1, 2, -1]
        [0, 1, 5]
     ]

Input 2:

 A = 11111
 B = [
        [0, 2, 4]
        [1, 2, -1
        [0, 2, 4]]
     ]



Example Output

Output 1:

 [2, 1, -1, 2]

Output 2:

 [1, -1, 1]



Example Explanation

Explanation 1:

 For query 1, binary string from index 3 to 5 is 010 = 2. So 2 mod 3 = 2.
 For query 2, binary string from index 3 to 4 is 01 = 1. So 1 mod 3 = 1.
 After query 3, given string changes to 11010.
 For query 4, binary string from index 1 to 5 is 11010 = 26. So 26 mod 3 = 2.
 So, output array is [2, 1, -1, 2].

Explanation 2:

 For query 1, binary string from index 2 to 4 is 111 = 7. So 7 od 3 = 1.
 After query 2, string remains same as there is already 1 at index 2.
 For query 3, binary string from index 2 to 4 is 111 = 7. So 7 od 3 = 1.
 So, output array is [1, -1, 1].
 */

    const int mod = 3;
    vector<int> tree;
    void build(vector<int> &a,int v,int l,int r){
        if(l==r)
            tree[v] = a[l];
        else{
            int mid = (l+r)/2;
            build(a,2*v,l,mid);
            build(a,2*v+1,mid+1,r);
            tree[v] = (tree[2*v]+tree[2*v+1])%3;
        }
    }
    int range_sum(int v,int tl,int tr,int l,int r){
        if(l>r)
            return 0;
        if(l==tl and r==tr)
            return tree[v];
        int tm = (tl+tr)/2;
        return (range_sum(2*v,tl,tm,l,min(tm,r))+range_sum(2*v+1,tm+1,tr,max(l,tm+1),r))%3;
    }
    void update(int v,int tl,int tr,int idx,int val){
        if(tl == tr)
            tree[v] = val;
        else{
            int tm = (tl+tr)/2;
            if(idx<=tm)
                update(2*v,tl,tm,idx,val);
            else
                update(2*v+1,tm+1,tr,idx,val);
            tree[v] = (tree[2*v]+tree[2*v+1])%3;
        }
    }
    vector<int> Solution::solve(string s, vector<vector<int> > &queries) {
        const int n = s.size();
        tree.assign(4*n,0);
        vector<int> power(n);
        vector<int> a(n);
        power[0] = 1;
        for(int i=1;i<n;i++){
            power[i] = (power[i-1]*2)%mod;
        }
        reverse(power.begin(),power.end());
        for(int i=0;i<n;i++){
            if(s[i]=='1')
                a[i] = power[i];
        }

        build(a,1,0,n-1);
        vector<int> ans;
        for(auto &q:queries){
            int x = q[0],u = q[1]-1,v = q[2]-1;
            if(x){
                if(s[u]=='0'){
                    s[u] = '1';
                    a[u] = power[u];
                    update(1,0,n-1,u,power[u]);
                }
                ans.push_back(-1);
            }else{
                int curr = range_sum(1,0,n-1,u,v);
                ans.push_back((curr*power[v])%3);
            }
        }
        return ans;
    }