All Tracks Data Structures Advanced Data Structures Segment Trees Problem

Binary Modulo <P2SME>
Tag(s):

Data Structures, Medium, Segment tree

Problem
Editorial
Analytics

You are given a Binary String A of length N indexed from 0 to \(N-1\). You have to perform 2 queries:-

  1. 0 L R - Tell the remainder of Number(in \(Decimal\)) represented by the Binary String between indexes L and R when divided by 5.
  2. 1 X V - Replace character at position X with V.

INPUT FORMAT
First line contains T which denotes the number of test cases.
The first line of each test case contains the binary string A.
The next line contains Q which is the number of queries.
Next Q lines contain the description of queries which may be of either of the 2 types as described in the problem statement.

OUTPUT FORMAT
For each query of Type 0, print the answer in a single line.

CONSTRAINTS

  • \(1 ≤ T ≤ 100\)
  • \(1 ≤ N,Q ≤ 10^{4}\)
  • \(0 ≤ L ≤ R < N\)
  • \(0 ≤ X < N\)
  • \(0 ≤ V ≤ 1\)


Hints for using the inbuilt code snippet
Let us take the example of sample input. So your function should return the output such that it resembles "0" + "\n" + "3" + "\n" + "2" + "\n" so that it correctly matches the output format as asked. You can use other alternatives too but the output format as rendered by the print function should match the format of sample out.


Note: It is not mandatory to use the code snippet that is provided to you in the editor by default. It is just to make the question more convenient. You can completely remove the default code and submit your solution in the appropriate format.

SAMPLE INPUT
1
01010101
5
0 1 3
1 2 1
0 2 5
1 3 1
0 0 7
SAMPLE OUTPUT
0
3
2
Explanation

For the 1st query, the Binary String is 101 i.e 5, hence remainder is 0.
For the 2nd query, Binary String is 1101 i.e 13, hence remainder is 3.

Time Limit: 5.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

Power2SME

Challenge Name

Power2SME PHP Hiring Challenge

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?