DCP-300: Shan and String Back to All Problems

Hard Data Structures > Segment Tree/Interval Tree

There is a little boy name Shan. One day he came up with a problem. Now you have to solve that problem. You will be given a Binary string S which contain either 0 or 1. Now you have to do two types of task. 1 x :- Change the value at x'th position. If the value is 1 then change it to 0 Or, if the value is 0 then change it to 1. (Toggle operation) 2 x y :- Find number of 1's block between two indexes x and y (inclusive). **A block of 1's is a maximal consecutive substring that only contains 1.** Input: ------- The first line of input contains integers N and M. N is the length of the string and M is the number of tasks to do. The Next line contains a string S. The Next M line contains a task either task 1 or 2. **( 1<=N<=100000 , 1<=M<=100000, 1<=x<=y<=N )** Output: ------- For each second type of task you have to output one integer representing it's result. Sample Input ------------ 10 5 1101011101 2 1 10 2 7 10 1 8 2 7 10 2 2 8 Sample Output ------------- 4 2 2 3

Problem Setter:

S.M. SHAHEEN SHA

Please login to submit solution to this problem.