Queries on the String  Problem code: QSET

SUBMIT MY SUBMISSIONS ALL SUBMISSIONS

All submissions for this problem are available.

Read problems statements in Mandarin Chinese and Russian.

You have a string of N decimal digits, denoted by numbers A₁,A₂, ..., A_N.

Now you are given M queries, each of whom is of following two types.

• Type 1: 1 X Y: Replace A_X by Y.
• Type 2: 2 C D: Print the number of sub-strings divisible by 3 of the string denoted by A_C,A_C+1 ...
  A_D.
  
  
  Formally, you have to print the number of pairs (i,j) such that the string A_i,A_i+1...A_j,
  (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 X_i, Y_i.
  For each query of type 2, next two integers denote C_i, D_i.

Output

For each query of type 2, print the required answer in a single line.

Constraints

• 0 ≤ A_i ≤ 9
• 1 ≤ X_i ≤ N
• 0 ≤ Y_i ≤ 9
• 1 ≤ C_i ≤ D_i ≤ N

Subtasks

• Subtask #1 (10 points): 1 ≤ N, M ≤ 10³ and only type 2 queries.
• Subtask #2 (15 points): 1 ≤ N, M ≤ 10³
• Subtask #3 (20 points): 1 ≤ N, M ≤ 10⁵ and only type 2 queries
• Subtask #4 (55 points): 1 ≤ N, M ≤ 10⁵

Example

Input:
5 3
01245
2 1 3
1 4 5
2 3 5

Output:
3
1

Explanation

For first query, the sub-strings S[1,1]="0", S[1,3]="012" and S[2,3]="12" are divisible by 3.
After second query, the string A becomes "01255".
For third query, only sub-string S[3,5]="255" is divisible by 3.

A very firm understanding of this question is the key to solve it .

For each node we require 4 things.    the number of substrings divisible by 3 on the segment , the total sum of the segment and the prefix and the suffix array .

where prefix array stands for the number of elements starting with the prefix and whose sum%3 gives 0,1 ,2. It is the same for prefix array. Now while ,merging two nodes , we first need to create the prefix and suffix arrays for the node. the prefix of a node is created by the total sum of the left child in combination with the prefix of the right child. the manner is given as:

(1) First we copy prefix array of the left child to the parent node.  then we combine it with the prefix of  the right array. Based on these conditions we use the prefix values on the right node.

(2) Similarly the suffix array of the parent node is calculated. 

(3) the total substrings in the parent is the sum of left and right node

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

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

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

we do the updates and queries similarly

     ********** here goes the code  ***************

#include<iostream>

#include<stdio.h>

#include<bits/stdc++.h>

using namespace std;

long long int arr[100010];

struct segment

{

 long long int count;

 long long int sum;

 long long int pre[4];

 long long int suf[4];

}tree[500000];

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

{

if(st>end)

return ;

if(st==end)

{

 tree[node].suf[(arr[st])%3]=1;

 tree[node].suf[(arr[st]+1)%3]=0;

           tree[node].suf[(arr[st]+2)%3]=0;

  tree[node].pre[arr[st]%3]=1;

  tree[node].pre[(arr[st]%3+2)%3]=0;

  tree[node].pre[(arr[st]+1)%3]=0;  

        if(arr[st]%3==0)

        tree[node].count=1;

        else

        tree[node].count=0;

        tree[node].sum=(arr[st]%3);

        return ;

}

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

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

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

tree[node].sum=(tree[2*node].sum+tree[2*node+1].sum)%3;

tree[node].pre[0]=tree[2*node].pre[0];

tree[node].pre[1]=tree[2*node].pre[1];

tree[node].pre[2]=tree[2*node].pre[2];

tree[node].suf[0]=tree[2*node+1].suf[0];

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

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

    if(tree[2*node].sum%3==0)

    {

     tree[node].pre[0]+=tree[2*node+1].pre[0];

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

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

}

else if(tree[2*node].sum%3==1)

{

tree[node].pre[0]+=tree[2*node+1].pre[2];

     tree[node].pre[1]+=tree[2*node+1].pre[0];

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

 

}

else

{

tree[node].pre[0]+=tree[2*node+1].pre[1];

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

 tree[node].pre[2]+=tree[2*node+1].pre[0];

}

if(tree[2*node+1].sum==0)

{

tree[node].suf[0]+=tree[2*node].suf[0];

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

tree[node].suf[2]+=tree[2*node].suf[2];

}

else if(tree[2*node+1].sum==1)

{

tree[node].suf[0]+=tree[2*node].suf[2];

tree[node].suf[1]+=tree[2*node].suf[0];

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

 

}

else

{

tree[node].suf[0]+=tree[2*node].suf[1];

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

tree[node].suf[2]+=tree[2*node].suf[0];

}

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

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

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

}

void update(int node, int st, int end,int range,long long int val)

{

if(st>end || st>range || end<range)

return ;

if(st==range && end==range)

{

arr[st]=(val)%3;;

 tree[node].suf[(arr[st])%3]=1;

 tree[node].suf[(arr[st]+1)%3]=0;

           tree[node].suf[(arr[st]+2)%3]=0;

  tree[node].pre[arr[st]%3]=1;

  tree[node].pre[(arr[st]%3+2)%3]=0;

  tree[node].pre[(arr[st]+1)%3]=0;  

        if(arr[st]%3==0)

        tree[node].count=1;

        else

        tree[node].count=0;

        tree[node].sum=(arr[st]%3);

        return ;

}

update(2*node,st,(st+end)/2,range,val);

update(2*node+1,(st+end)/2+1,end,range,val);

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

tree[node].sum=(tree[2*node].sum+tree[2*node+1].sum)%3;

tree[node].pre[0]=tree[2*node].pre[0];

tree[node].pre[1]=tree[2*node].pre[1];

tree[node].pre[2]=tree[2*node].pre[2];

tree[node].suf[0]=tree[2*node+1].suf[0];

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

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

    if(tree[2*node].sum%3==0)

    {

     tree[node].pre[0]+=tree[2*node+1].pre[0];

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

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

}

else if(tree[2*node].sum%3==1)

{

tree[node].pre[0]+=tree[2*node+1].pre[2];

     tree[node].pre[1]+=tree[2*node+1].pre[0];

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

 

}

else

{

tree[node].pre[0]+=tree[2*node+1].pre[1];

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

 tree[node].pre[2]+=tree[2*node+1].pre[0];

}

if(tree[2*node+1].sum==0)

{

tree[node].suf[0]+=tree[2*node].suf[0];

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

tree[node].suf[2]+=tree[2*node].suf[2];

}

else if(tree[2*node+1].sum==1)

{

tree[node].suf[0]+=tree[2*node].suf[2];

tree[node].suf[1]+=tree[2*node].suf[0];

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

 

}

else

{

tree[node].suf[0]+=tree[2*node].suf[1];

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

tree[node].suf[2]+=tree[2*node].suf[0];

}

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

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

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

}

segment query(int node, int st, int end,int qs, int qe)

{

if(st>end || st>qe || end<qs)

    {

     segment temp;

     temp.count=0;

     temp.sum=0;

     temp.pre[0]=0;temp.pre[1]=0;

     temp.pre[2]=0; temp.suf[0]=0;temp.suf[1]=0;temp.suf[2]=0;

     return temp;

}

if(st>=qs && end<=qe)

{

return tree[node];

}

segment q1=query(2*node,st,(st+end)/2,qs,qe);

segment q2=query(2*node+1,(st+end)/2+1,end,qs,qe);

segment q3;

q3.count=q1.count+q2.count;

q3.sum=(q1.sum+q2.sum)%3;

q3.pre[0]=q1.pre[0];

q3.pre[1]=q1.pre[1];

q3.pre[2]=q1.pre[2];

q3.suf[0]=q2.suf[0];

q3.suf[1]=q2.suf[1];

q3.suf[2]=q2.suf[2];

    if(q1.sum%3==0)

    {

     q3.pre[0]+=q2.pre[0];

     q3.pre[1]+=q2.pre[1];

 q3.pre[2]+=q2.pre[2];

}

else if(q1.sum%3==1)

{

q3.pre[0]+=q2.pre[2];

     q3.pre[1]+=q2.pre[0];

 q3.pre[2]+=q2.pre[1];

 

}

else

{

q3.pre[0]+=q2.pre[1];

     q3.pre[1]+=q2.pre[2];

 q3.pre[2]+=q2.pre[0];

}

if(q2.sum==0)

{

q3.suf[0]+=q1.suf[0];

q3.suf[1]+=q1.suf[1];

q3.suf[2]+=q1.suf[2];

}

else if(q2.sum==1)

{

q3.suf[0]+=q1.suf[2];

q3.suf[1]+=q1.suf[0];

q3.suf[2]+=q1.suf[1];

 

}

else

{

q3.suf[0]+=q1.suf[1];

q3.suf[1]+=q1.suf[2];

q3.suf[2]+=q1.suf[0];

}

q3.count+=q1.suf[0]*q2.pre[0];

q3.count+=q1.suf[1]*q2.pre[2];

q3.count+=q1.suf[2]*q2.pre[1];

return q3;

}

char str[100010];

int main()

{

int n;

int q;

cin>>n;

cin>>q;

cin>>str;

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

{

arr[i]=str[i]-'0';

}

build(1,0,n-1);

/* for(int i=1;i<=9;i++)

{

//  cout<<"nocd "<<" "<<i<<endl;

// cout<<"pre "<<tree[i].pre[0]<<" "<<tree[i].pre[1]<<" "<<tree[i].pre[2]<<endl;

 //cout<<" suff  "<<tree[i].suf[0]<<" "<<tree[i].suf[1]<<" "<<tree[i].suf[2]<<endl;

 cout<<i<<" "<<tree[i].count<<endl;

}*/

long long int val;int range;

while(q--)

{

int tp;

// cin>>tp;

scanf("%d",&tp);

if(tp==1)

{

 //cin>>range>>val;

 scanf("%d",&range);

 scanf("%lld",&val);

 update(1,0,n-1,range-1,val);

}

else

{

int qs,qe;

//cin>>qs>>qe;

scanf("%d %d",&qs,&qe);

segment ans;

ans=query(1,0,n-1,qs-1,qe-1);

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

}

}

return 0;

}

******** code ends here****