# Help | Query to find longest subarray containing all 1's

#1

You are given a string of size n consisting of 0s and/or 1s. You have to perform total k queries and there are two types of queries possible:

1. “1” (without quotes): Print length
of the longest sub-array which
consists of all ‘1’.
2. “2 X” (without quotes): where X is
an integer between 1 to n. In this
query, you will change character at
the Xth position to ‘1’ (It is
possible that the character at i-th

Input Format

First line of input contains n and k, where n is the length of the string, k is the number of queries.
Next line contains a string of 0’s and/or 1’s of length n.
Each of next k lines contains query of any one type(i.e 1 or 2).

Input Constraints

• 1≤n,k≤10^5

• 1≤X≤n

• String contains only 0s and/or 1s.

• Each query is of one of the mentioned
types.

Output Format

For each query of type 1, print in a new line the maximum size of the subarray with all 1’s

Sample Input

``````5 7
00000
1
2 3
1
2 5
1
2 4
1
``````

Sample Output

``````0
1
1
3
``````

Explanation

• Initially there are no 1’s in the string, hence the answer is 0.
• In second query of type ‘1’ state of string is 00100, hence answer is 1.
• In Third query of type ‘1’ state of string is 00101, hence answer is 1.
• In Fourth query of type ‘1’ state of string is 00111, hence answer is 3.

Can someone tell me how to approach this question?

#2

Do it using segment tree.

Each node of segment tree stores three things,ans for this node,maximum conseutive prefix 1’s,maximum consecutive suffix 1’s

Now comes merging

ans*=max(ans[2i+1],ans[2i+2],suffixMax[2i+1]+PrefixMax[2i+2])

(ans for this node can come either from left part,or right part,or both combined)

SuffixMax*=max(SuffixMax[2i+2])
if(SuffixMax[2
i+2]==(number of elements n that range)
suffixMax*=max(suffixMax*,suffixMax[2i+1]+suffixMax[2i+2])

Same for prefix

#3

#4

implementation of @vivek_1998299 idea! : https://ideone.com/v9fg9A

#5

another approach : https://ideone.com/C0VEkN

The idea is to maintain start and end of the block(the sub-array having all 1’s) and when any update comes just see the previous position and the next position. If any of them is 1 then update start and end accordingly.

Please comment if something is not clear.

#6

@pk301 If i am not wrong your solution is n^2. (Correct me if I am wrong)
Test case :
n = 1e5; (string containing all zeroes)
q = 1e5;
for(int i = q; i > 0; --i) {
query of second type
2 i
}

#7

Could you please explain it with the help of relevant example?

#8

Ohk,the only thing here to understand is how to merge

so,

lets say we are at node i,

node 2*i+1 covers a part of array lets say 1 0 1 1 (range [1-4])

node 2*i+2 covers a part of array lets say 1 1 1 0 (range [5-8])

So ans[2i+1]=2,ans[2i+2]=3,SuffixMax[2i+1]=2,suffixMax[2i+2]=0,PreixMax[2i+1]=1,prefixMax[2i+2]=3

So to calculate ans* either i can take 2(range[3-4] from 2i+1) or 3(range[5-7] from 2i+2) or some range which lies in both parts

#9

So that would be suffixMax[2i+1](range(3-4) from 2i+1) +prefixMax[2i+2](range(5-7) from 2i+2) ->ie range(3-7)—>5

so ans is max(2(from left),3(from right),5(from both))=5

and suffixMax and prefixMax i think is pretty easy to understand(if u dont get it then ask)

#10

I am not completely sure if this works or not, but we can simply edit all 0’s to -INF(-1e6) and apply maximum subarray sum using Segment Tree like in this problem(www.spoj.com/problems/GSS1)!

#11

Btw the approach would be mostly similar to what @vivek_1998299 said.

#12

Can you provide a link to the question pls. I would like to try it out!

#13

@dishant_18 yeah right we can do this too

#14

Your approach is also quite interesting. Btw our merge function will be quite a lot similar xD… Hope we don’t get caught in plagiarism lol!

#15

Please don’t post any irrelevant comment here. Refrain yourself by posting these ones in future.

#16

Link has been expired, that’s why I had written the whole question from myself.

#17

Thanx liked the editorial method.

#18

Segment Trees with a slight modification