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

help
array

#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*=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

here is the question link


#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.

This discussion forum ain’t your Facebook or Whatsapp.


#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 :slight_smile: