QUERIES ON THE STRING

• Problem Description

  
  "You have a string of N decimal digits, denoted by numbers A1,A2, ..., AN.
  
  Now you are given M queries, each of whom is of following two types.
  
  
  Type 1: 1 X Y: Replace AX by Y.
  Type 2: 2 C D: Print the number of sub-strings divisible by 3 of the string denoted by AC,AC+1 ...
  AD.
  
  
  Formally, you have to print the number of pairs (i,j) such that the string Ai,Ai+1...Aj,
  (C i j D), when considered as a decimal number, is divisible by 3. 
  Input
  
  There is only one test case.
  First line of input contains two space separated integers N, M.
  Next line contains a string of N digits, denoting string A.
  For next M lines, each line contains a query.
  Each query is given by three space separated integers.
  The first integer denotes type of the query. For each query of type 1, next two integers denote Xi, Yi.
  For each query of type 2, next two integers denote Ci, Di.
  Output
  
  For each query of type 2, print the required answer in a single line.
  
  Constraints
  
  0 <=Ai <= 9
  1<= Xi <= N
  0 <= Yi <= 9
  1 <= Ci Di <=N
  Subtasks
  
  Subtask #1 (10 points): 1 N, M 103 and only type 2 queries.
  Subtask #2 (15 points): 1 N, M 103
  Subtask #3 (20 points): 1 N, M 105 and only type 2 queries
  Subtask #4 (55 points): 1 N, M 105"

• CODING ARENA::

• #include <stdio.h>

  #include<stdlib.h>

  #include<string.h>

  #include<math.h> 

  #include<stdbool.h>

  static long long int a[100010];

  static long long int b[262244][3];

  static long long int c[262244][3];

  static long long int d[262244];

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

  {if(start==end)

   {b[curr][(a[end]-a[start-1])%3]++; 

    c[curr][(a[end]-a[start-1])%3]++;

    d[curr]=a[start]-a[start-1];

    return;

   } 

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

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

   long long int i=a[(start+end)/2]-a[start-1];i%=3;

   b[curr][0]=b[2*curr][0];b[curr][1]=b[2*curr][1];b[curr][2]=b[2*curr][2];

   if(i==0)

   {b[curr][0]+=b[2*curr+1][0];b[curr][1]+=b[2*curr+1][1];b[curr][2]+=b[2*curr+1][2];     

   }

   else if(i==1)

    {b[curr][0]+=b[2*curr+1][2];b[curr][1]+=b[2*curr+1][0];b[curr][2]+=b[2*curr+1][1];          

    }

   else

    {b[curr][0]+=b[2*curr+1][1];b[curr][1]+=b[2*curr+1][2];b[curr][2]+=b[2*curr+1][0];     

    }

   i=a[end]-a[(start+end)/2];i%=3;

   c[curr][0]=c[2*curr+1][0];c[curr][1]=c[2*curr+1][1];c[curr][2]=c[2*curr+1][2];

    if(i==0)

   {c[curr][0]+=c[2*curr][0];c[curr][1]+=c[2*curr][1];c[curr][2]+=c[2*curr][2];     

   }

   else if(i==1)

    {c[curr][0]+=c[2*curr][2];c[curr][1]+=c[2*curr][0];c[curr][2]+=c[2*curr][1];          

    }

   else

    {c[curr][0]+=c[2*curr][1];c[curr][1]+=c[2*curr][2];c[curr][2]+=c[2*curr][0];     

    }

   d[curr]=d[2*curr]+d[2*curr+1];

  }

   

  void update(int start,int end,int x,int y,int curr,int data)

  {if(start>end || end<x || start>y)

      return;

   else if(start>=x && end<=y)

   {b[curr][0]=0;

    b[curr][1]=0;

    b[curr][2]=0;

    c[curr][0]=0;

    c[curr][1]=0;

    c[curr][2]=0;

    b[curr][data%3]++;

    c[curr][data%3]++;

       d[curr]=data;

   return;

   }

   update(start,(start+end)/2,x,y,2*curr,data);

   update((start+end)/2+1,end,x,y,2*curr+1,data);

   d[curr]=d[2*curr]+d[2*curr+1];

   long long int i=d[2*curr];i%=3;

   b[curr][0]=b[2*curr][0];b[curr][1]=b[2*curr][1];b[curr][2]=b[2*curr][2];

   if(i==0)

   {b[curr][0]+=b[2*curr+1][0];b[curr][1]+=b[2*curr+1][1];b[curr][2]+=b[2*curr+1][2];     

   }

   else if(i==1)

    {b[curr][0]+=b[2*curr+1][2];b[curr][1]+=b[2*curr+1][0];b[curr][2]+=b[2*curr+1][1];          

    }

   else

    {b[curr][0]+=b[2*curr+1][1];b[curr][1]+=b[2*curr+1][2];b[curr][2]+=b[2*curr+1][0];     

    }

   i=d[2*curr+1];i%=3;

   c[curr][0]=c[2*curr+1][0];c[curr][1]=c[2*curr+1][1];c[curr][2]=c[2*curr+1][2];

    if(i==0)

   {c[curr][0]+=c[2*curr][0];c[curr][1]+=c[2*curr][1];c[curr][2]+=c[2*curr][2];     

   }

   else if(i==1)

    {c[curr][0]+=c[2*curr][2];c[curr][1]+=c[2*curr][0];c[curr][2]+=c[2*curr][1];          

    }

   else

    {c[curr][0]+=c[2*curr][1];c[curr][1]+=c[2*curr][2];c[curr][2]+=c[2*curr][0];     

    }

  }

  long long int a1,a2,a3,ss;

  void sum(int start,int end,int x,int y,int curr)

  {if(start>end || end<x || start>y)

      return;

   if(start>=x && end<=y)

   {if(ss==-1)

    {

     ss=d[curr];

     a1=b[curr][0];a2=b[curr][1];a3=b[curr][2];

    }

    else

   {ss%=3;

    if(ss==0)

    {a1+=b[curr][0];a2+=b[curr][1];a3+=b[curr][2];

    }

    else if(ss==1)

    {a1+=b[curr][2];a2+=b[curr][0];a3+=b[curr][1];      

    }

    else

    {a1+=b[curr][1];a2+=b[curr][2];a3+=b[curr][0];

    }

    ss+=d[curr];

   }

    return;

   }

   sum(start,(start+end)/2,x,y,2*curr);

   sum((start+end)/2+1,end,x,y,2*curr+1);

  }    

  int main()

  {int i,n,m;

   char ch[100010];

   scanf("%d %d",&n,&m);

   scanf("%s",ch);

   for(i=1;i<=n;i++)

   {a[i]=a[i-1]+ch[i-1]-'0';     

   }build(1,n,1);

   int c,x,y;

   long long int ans;

   while(m--)

   {scanf("%d %d %d",&c,&x,&y);

       if(c==1)

           update(1,n,x,x,1,y);

      else

      {ss=-1;a1=0;a2=0;a3=0;

       sum(1,n,x,y,1);

       ans=0;

       if(a1>=1)

           ans=ans+(a1*(a1+1))/2;

       if(a2>=1)

          ans=ans+(a2*(a2-1))/2;

      if(a3>=1)

          ans=ans+(a3*(a3-1))/2;

           

           printf("%lld\n",ans);

      }     

   }

    return 0;

  }

     

• Test Case 1

  
  Input (stdin)

  5 3
  
  01245
  
  2 1 3
  
  1 4 5
  
  2 3 5
  
  

  Expected Output

  3
  
  1

• Test Case 2

  
  Input (stdin)

  5 3
  
  01245
  
  2 1 5
  
  1 4 4
  
  2 2 5
  
  

  Expected Output

  7
  
  4