Queries on the String

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_{1},A_{2}, ..., 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 substrings 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^{3} and only type 2 queries.
 Subtask #2 (15 points): 1 ≤ N, M ≤ 10^{3}
 Subtask #3 (20 points): 1 ≤ N, M ≤ 10^{5} and only type 2 queries
 Subtask #4 (55 points): 1 ≤ N, M ≤ 10^{5}
Example
Input: 5 3 01245 2 1 3 1 4 5 2 3 5 Output: 3 1
Explanation
For first query, the substrings 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 substring S[3,5]="255" is divisible by 3.
Author:  darkshadows 
Tester:  shiplu 
Editorial  http://discuss.codechef.com/problems/QSET 
Tags  darkshadows, jan15, medium, numbertheory, segmenttree 
Date Added:  28052014 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions