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

help
,
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
    position was already ‘1’).

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[i]=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[i]=max(SuffixMax[2i+2])
if(SuffixMax[2i+2]==(number of elements n that range)
suffixMax[i]=max(suffixMax[i],suffixMax[2i+1]+suffixMax[2i+2])

Same for prefix

2 Likes
3

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

4

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[i] 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

5

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)

6

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)!

1 Like
7

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

8

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

9

@dishant_18 yeah right we can do this too

1 Like
10

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!

11

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

This discussion forum ain’t your Facebook or Whatsapp.

12

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

13

here is the question link

1 Like
14

Thanx liked the editorial method.

15

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

1 Like
16

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.

17

@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
}