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

S.M. SHAHEEN SHA

Language |
Time Limit (seconds) |

C | 2.00 |

C++ | 2.00 |

C++14 | 2.00 |

C# | 3.00 |

Go | 3.00 |

Java | 3.00 |

JavaScript | 3.00 |

Objective-C | 3.00 |

Perl | 3.00 |

PHP | 3.00 |

Python | 3.00 |

Python3 | 3.00 |

Ruby | 3.00 |

VB.Net | 3.00 |

Solve/Submission

# | User | Language | Timing |
---|---|---|---|

01 | Morass | Cpp14 | 0.02s |

02 | Nezz | Cpp | 0.03s |

03 | njrafi | Cpp14 | 0.03s |

04 | feodorv | Cpp14 | 0.03s |

05 | GustavoCandido | Cpp14 | 0.04s |

06 | ksohan | Cpp14 | 0.04s |

07 | jahid_ict | Cpp14 | 0.04s |

08 | last_man | Cpp14 | 0.04s |

09 | heiseish | Cpp | 0.05s |

10 | Robbinb1993 | Cpp14 | 0.05s |

11 | ____ | Cpp14 | 0.05s |

12 | fsshakkhor | Cpp14 | 0.05s |

13 | Nirjhor | Cpp14 | 0.05s |

14 | khatribiru | Cpp14 | 0.05s |

15 | sayedgkm | Cpp14 | 0.06s |

16 | mamun4122 | Cpp14 | 0.06s |

17 | rubabredwan | Cpp14 | 0.06s |

18 | sahedsohel | Cpp14 | 0.06s |

19 | ehsan_sshuvo96 | Cpp | 0.06s |

20 | tariqiitju | Cpp | 0.06s |

21 | Sarwar05 | Cpp14 | 0.06s |

22 | Protap_Ghose | Cpp14 | 0.06s |

23 | Jisancse | Cpp | 0.06s |

24 | Rajib_119 | Cpp14 | 0.07s |

25 | adamantium | Cpp14 | 0.07s |

26 | imAnik | Cpp14 | 0.07s |

27 | Tahmid | Cpp | 0.07s |

28 | _dipu | Cpp14 | 0.07s |

29 | Double_O | Cpp14 | 0.08s |

30 | as_couple | Cpp14 | 0.09s |

31 | acraider | Cpp14 | 0.10s |

32 | skmonir | Cpp14 | 0.11s |

33 | seyedssz | Cpp14 | 0.12s |

34 | nasib_mbstu | Cpp | 0.13s |

35 | Digonta | Cpp | 0.15s |

36 | I_See_You | Cpp14 | 0.20s |

Copyright © 2015-2016 Dev Skill.

Feedback
#### Your feedback is our precious!

## Thank you for providing feedback! Our developers will be happy :)

## Sorry there was a problem when submitting the feedback. Please try again. :(