***2 vs 3.

            2 vs 3.
The fight for the best number in the globe is going to finally come to an end.The top two contenders for the best number are number 2 and number 3.It's the final the entire world was waiting for. Expectorates from all across the globe came to witness the breath taking finals.

The finals began in an astonishing way.A common problem was set for both of them which included both these number.The problem goes like this.

Given a binary string (that is a string consisting of only 0 and 1). They were supposed to perform two types of query on the string.

Type 0: Given two indices l and r.Print the value of the binary string from l to r modulo 3.

Type 1: Given an index l flip the value of that index if and only if the value at that index is 0.

The problem proved to be a really tough one for both of them.Hours passed by but neither of them could solve the problem.So both of them wants you to solve this problem and then you get the right to choose the best number in the globe.

Input:

The first line contains N denoting the length of the binary string .The second line contains the N length binary string.Third line contains the integer Q indicating the number of queries to perform.This is followed up by Q lines where each line contains a query.

Output:

For each query of Type 0 print the value modulo 3.

Constraints:

1<= N <=10^5

1<= Q <= 10^5

0 <= l <= r < N

Sample Input(Plaintext Link)
 5
10010
6
0 2 4
0 2 3
1 1
0 0 4
1 1
0 0 3
Sample Output(Plaintext Link)
 2
1
2
1
Explanation
Query 1 : This is of type 0. The binary string is 010 which is equal to 2 and 2%3=2. So answer is 2.

Query 2 : This is of type 0. The binary string is 01 which is equal to 1 ( (2^1) * 0 +(2^0) * 1 ) =0 + 1 =1) and 1%3=1. So answer is 1.

Query 3 : This is of type 1. The value at index 1 is 0 so we flip it .The new string is 11010.

Query 4 : This is of type 0. The binary string is 11010 ( (2^0) * 0 +(2^1) * 1 +(2^2) * 0 +(2^3) * 1 +(2^4) * 1 = 2 + 8 +16 =26 ) which is equal to 26 and 26%3=2. So answer is 2.

Query 5 : This is of type 1. The value at index 1 is 1 so we do nothing .The new string is 11010.

Query 6 : This is of type 0. The binary string is 1101 ( (2^0) * 1 +(2^1) * 0 +(2^2) * 1 +(2^3) * 1 = 1 + 4+ 8 =13 ) which is equal to 13 and 13%3=1. So answer is 1.


-----------------------------------------------------code---------------------------------------------------------------

Problem 2 vs 3

Subproblem: How to compute the value of binary string S[0..9] modulo 3 efficiently if we know the corresponding value for S[0..4] and S[5..9] ?
Solution: let value of S[0..4] be x and S[5..9] be y. Then value of S[0..9] will be x*(2⁵)+y.

Complete Solution Approach
Maintain a segment tree : tree[i] stores the value of the binary substring si to sj modulo 3.
Updates:
How to modify q^th bit to 1. When modifying tree[i], update the corresponding child (i.e. tree[2i] responsible for [si..mid]or tree[2i+1] responsible for [mid+1..sj] ). When we have modified the child, now we want to calculate correct value of [si..sj]. Remember we have value of [si..mid] and [mid+1...sj].
Therefore, by our subproblem, tree[i] = tree[2i] * 2^sj-mid + tree[2i+1] mod 3.
Queries:
Queries can be answered similarly by this divide and conquer approach.

Time Complexity
O(log N) update and O(log N) query. => O(Q*log N)

---------------------------------------------------------------code------------------------------------------------------------------------------------

#include<iostream>

#include<bits/stdc++.h>

using namespace std;

int arr[1010000];

struct abc

{

int count ;

int val;

}  tree[1010000];

/* Function to calculate x raised to the power y in O(logn)*/

int power(int x,  int y)

{

    int temp;

    if( y == 0)

        return 1;

    temp = power(x, y/2);

    temp%=3;

    if (y%2 == 0)

        return (temp*temp)%3;

    else

        return (x*temp*temp)%3;

}

abc query(int node,int start,int end,int r1,int r2)

 {

   //cout<<start<<"      "<<end<<endl;

  if(start>end || r1>end || r2<start) 

  {

  abc no;

  no.count=0;

  no.val=0;

  return no;

  }

   

   if(r1<=start && r2>=end)

    {

    // cout<<"  returnss "<<tree[node].count<<" "<<tree[node].val<<endl;

     return tree[node];

     

    }

    else

    {

     abc q1=query(2*node,start,(start+end)/2,r1,r2);

     abc q2=query(2*node+1,((start+end)/2)+1,end,r1,r2);

      abc d;

    

    d.count=q1.count+q2.count;

    d.val=(q1.val*power(2,q2.count)+q2.val);

    d.val%=3;

    if(d.val<0)d.val+=3;

   // cout<<"  return "<<d.count<<" "<<d.val<<endl;

    return d;

    }

 }

void update(int node ,int start,int end,int r1,int r2,int val)

 {

  //cout<<"update "<<start<<" "<<end<<endl;

  if(r1>end  || r2<start   || start>end) return  ;

  

  

  if(r1<=start && r2>=end)

   {

     tree[node].count=1;

     tree[node].val=1;

    

   }

   else

   {

    update(2*node, start,(start+end)/2,r1,r2,val);

    update(2*node+1, ((start+end)/2)+1,end,r1,r2,val);

      tree[node].count=tree[2*node].count+tree[2*node+1].count;

          tree[node].val=tree[2*node].val*power(2,tree[2*node+1].count)+tree[2*node+1].val;

          tree[node].val%=3;

    if(tree[node].val<0) tree[node].val+=3;

          

   }

    

   

 }  

void build(int node , int start,int end)

 {

 // cout<<start<<"            "<<end<<endl;

  if(start==end) 

  {

 

  tree[node].count=1;

 

  tree[node].val=arr[start];

  // cout<<"  node "<<node<<" count "<<tree[node].count<<" val "<< tree[node].val<<endl;

  }

  else if(start>end) return ;

  else

   {

   

    build(2*node,start,(start+end)/2);

    build(2*node+1,((start+end)/2)+1,end);

    

    tree[node].count=tree[2*node].count+tree[2*node+1].count;

    tree[node].val=(tree[2*node].val*power(2,tree[2*node+1].count)+tree[2*node+1].val);

    tree[node].val%=3;

    if(tree[node].val<0) tree[node].val+=3;

//    cout<<"  node "<<node<<" count "<<tree[node].count<<" val "<< tree[node].val<<endl;

   }

   

 }

int main()

 {

  //freopen("abc.txt","w",stdout);

   int n;

    cin>>n;

     char cc[1000+n];

      cin>>cc;

      int pp=0;

      for(int i=0;i<n;i++)

      {

      if(cc[i]=='0') arr[i]=0;

      else arr[i]=1;

 }

    // for(int i=0;i<n;i++) cout<<arr[i]<<" ";

     // cout<<endl;

     for(int i=0;i<3*n;i++)

      {

      tree[i].count=0;

      tree[i].val=0;

 }

       build(1,0,n-1);

       

      int q;

       cin>>q;

        while(q--)

         {

          int inp;

           cin>>inp;

           if(inp==1)

           {

            int index;

            cin>>index;

            if(arr[index]==0)

            {

            arr[index]=1;

            update(1,0,n-1,index,index,1);

}

  }

  else

  

             {

              int r1,r2;

               cin>>r1>>r2;

              //  cout<<"call"<<(n-1-r2)<<" "<<(n-1-r1)<<endl;

              abc res= query(1,0,n-1,r1,r2);

              

               cout<<res.val%3<<endl;

             }

         }

       

  return 0;

 }

**Monk and Otakuland

         Monk and Otakuland

Problem

Monk lives in Otakuland. Otakuland consists of N vertices and N-1 directed edges. i-th edge is a directed edge either from i-th vertex to i+1-th vertex or from i+1-th vertex to i-th vertex. You are given M Queries. Queries are 2 types:

1. 1 l r - Reverse the direction of the edges between l-th vertex and r-th vertex.
2. 2 f t - Output the minimum number of edges which you have to reverse the direction to arrive from f to t.

Input:

The first line contains two integers N, the number of vertices and M, the number of queries. The next line will containsN-1 characters which represent the direction of the edges. i-th character is either '>' or '<': '>' represents that only i -> i+1is valid, '<' represents that only i+1 -> i is valid. The following M lines will each contain a query like the ones mentioned above.

Output:

For query 2, print the answer in a new line.

Constraints:

2 ≤ N ≤ 200000
1 ≤ M ≤ 200000
1 ≤ l < r ≤ N
1 ≤ f , t ≤ N

---

Sample Input

(Plaintext Link)

6 6
>><<>
2 1 6
2 6 1
1 3 5
2 1 6
1 1 6
2 6 1

Sample Output

(Plaintext Link)

2
3
0
0

Explanation

In the sample testcase the graph is like this, 1->2->3<-4<-5->6. At the first query, Monk have to reverse the direction of 3rd edge and 4th edges to arrive from 1st vertex to 6th vertex. Second, Monk have to reverse the direction of 1st, 2nd, and 5th edges to arrive from 6th vertex to 1st vertex. Third, Reverse the direction of the edges between 3rd vertex and 5th vertex. After the query, graph is like this, 1->2->3->4->5->6. Fourth, Monk don't have to reverse the direction of any edge. Fifth, Reverse the direction of the edges between 1st vertex and 6th vertex. After the query, graph is like this, 1<-2<-3<-4<-5<-6. Sixth, Monk don't have to reverse the direction of any edge.

------------------------------------------editorial-------------------------------------------------------------------------------------------------------------

Reach-ability of t from f
All the edges between f to t must be in the direction from f towards *t.
Lets say f<t, then all the edges must be towards the right. The edges we need to reverse are those edges that are in the opposite direction from t towards *f.

Thus the answer to any query is the count of edges that are in direction from t towards f. Without loss of generality assume f<t. The answer would be the number of edges in the left direction.

Thus to solve this problem we need to maintain the direction of each edge and efficiently count the number of edges facing left in any queried range.
The two tasks can be done easily using segment tree with lazy propagation ( as there are range updates and range queries). Any node of segment tree can store the number of edges in the left direction in its responsibility range. We can deal with updates lazily.
The case when f>t can be similarly answered. Just count the number of edges facing right =( total edges in between fand t) - (total edges facing left in the same range).

Thus there is O(log N) per update and O(log N) per query making it O(N + Q * log N) final time complexity.

-------------------------------------------------------------------------code----------------------------------------------------------------------------------

#include<iostream>

using namespace std;

int arr[6010000];

#define inf 999999999

struct st

 {

  int     zero;

  int one;

 } 

 tree[6000000];

 

 int lazy[6000000];

int  ans=0;

  int read_int(){

char r;

bool start=false,neg=false;

int ret=0;

while(true){

r=getchar();

if((r-'0'<0 || r-'0'>9) && r!='-' && !start){

continue;

}

if((r-'0'<0 || r-'0'>9) && r!='-' && start){

break;

}

if(start)ret*=10;

start=true;

if(r=='-')neg=true;

else ret+=r-'0';

}

if(!neg)

return ret;

else

return -ret;

}

int query(int node,int start,int end,int r1,int r2,int  tt)

 {

  //   cout<<start<<" "<<end<<endl;

  //  cout<<" r1 "<<r1<<" r2 "<<r2<<endl;

 

  

   if(lazy[node])

   {

       if(lazy[node]%2==1)

       {

        int temp=tree[node].zero;

         tree[node].zero=tree[node].one;

         tree[node].one=temp;

            lazy[2*node]+=lazy[node];

             lazy[2*node+1]+=lazy[node];

     

  }

  lazy[node]=0;

         

   }

   if(start>end || r1>end || r2<start || r1>r2) return 0;

   if(r1<=start && r2>=end)

    {

    // cout<<"here "<<node<<endl;

    if(tt==1)

    {

    // cout<<" returning       "<<tree[node].zero<<endl;

    ans+=tree[node].zero;

    return tree[node].zero;

     

}

    

     else

     {//

      // cout<<"  returning       "<<tree[node].one<<endl;

      ans+=tree[node].one;

      return tree[node].one;

       

     

}

     

     

    }

    else

    {

     int q1=query(2*node,start,(start+end)/2,r1,r2,tt);

     int q2=query(2*node+1,((start+end)/2)+1,end,r1,r2,tt);

 

     return (q1+q2);

    }

 }

 

 

void update(int node ,int start,int end,int r1,int r2,int val)

 {

 

 // cout<<" update in the range "<<start<<" "<<end<<endl;

  

  if(lazy[node]!=0)

   {

    // cout<<" lazy node "<<node<<endl;

   

     int times=lazy[node];

    // cout<<" lazy node "<<node<<" times "<<times<<endl;

     times%=2;

     

     if(times==1)

     {

      int temp=tree[node].zero;

      tree[node].zero=tree[node].one;

      tree[node].one=temp;

       

     // cout<<" making lazing "<<2*node<<" "<<2*node+1<<endl;

         lazy[2*node+1]+=1;

         lazy[2*node]+=1;

          

}

 

    lazy[node]=0;

    

   }

   

   

    if(r1>end  || r2<start   || start>end) return  ;

  if(r1<=start && r2>=end)

   {

   

     int temp=tree[node].zero;

      tree[node].zero=tree[node].one;

      tree[node].one=temp;

     if(start!=end)

      {

     

       lazy[2*node]+=1;

       lazy[2*node+1]+=1;

      //  cout<<" making lazing "<<2*node<<" "<<2*node+1<<endl;

      }

      return  ;

   }

   

    update(2*node, start,(start+end)/2,r1,r2,val);

    update(2*node+1, ((start+end)/2)+1,end,r1,r2,val);

    // cout<<" finalizing node "<<node<<endl;

     tree[node].zero=tree[2*node].zero+tree[2*node+1].zero;

    tree[node].one=tree[2*node].one+tree[2*node+1].one;

   

 }

 

 

void build(int node , int start,int end)

 {

 

  if(start==end)

  {

  if(arr[start]==1)

  {

  tree[node].zero=0;

  tree[node].one=1;

  }

  else

  {

  tree[node].zero=1;

  tree[node].one=0;

  }

  // cout<<"  at nod"<<node<<"  zero          "<<tree[node].zero<<" one      "<<tree[node].one<<endl;

   }

  else if(start>end) return ;

  else

   {

    build(2*node,start,(start+end)/2);

    build(2*node+1,((start+end)/2)+1,end);

    tree[node].zero=tree[2*node].zero+tree[2*node+1].zero;

    tree[node].one=tree[2*node].one+tree[2*node+1].one;

  

   }

   

 }

 

 

int main()

 {

  

   int n,q;

   // cin>>n>>q;

   n=read_int();

   q=read_int();

    

    char ae[10000+n];

    cin>>ae;

     for(int i=0;i<n-1;i++)

     {

     

     

       

       if(ae[i]=='>')arr[i]=1;

       else   arr[i]=0;

     

}

 

      for(int i=0;i<2*n+100;i++)

       {

        tree[i].zero=0;

        tree[i].one=0;

  }

  

       build(1,0,n-2);

 

       

    

        while(q--)

         {

          ans=0;

            int typ,l,r;

          // cin>>typ>>l>>r;

           typ=read_int();

            l=read_int();

             r=read_int();

             if(typ==2)

             {

              int res;

              if(l<=r)

              res=query(1,0,n-2,l-1,r-2,1);

              else

              {

             

              res=query(1,0,n-2,r-1,l-2,0);

               

}

              cout<<ans<<endl;

               

}

else

{

int val=0;

    update(1,0,n-2,l-1,r-2,val);

}

              

              

             

         }

       

  return 0;

 }