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.

Problem Limits

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

Problem Stats

50/139

Solve/Submission

Ranking

# 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 addu621 Cpp14 0.06s
25 Tahmid Cpp 0.07s
26 _dipu Cpp14 0.07s
27 Rajib_119 Cpp14 0.07s
28 adamantium Cpp14 0.07s
29 imAnik Cpp14 0.07s
30 Double_O Cpp14 0.08s
31 as_couple Cpp14 0.09s
32 acraider Cpp14 0.10s
33 skmonir Cpp14 0.11s
34 seyedssz Cpp14 0.12s
35 nasib_mbstu Cpp 0.13s
36 Digonta Cpp 0.15s
37 I_See_You Cpp14 0.20s
Feedback

Your feedback is our precious!



Or call +88 02 9853138 for support