Is it possible to solve this problem with a bitset?

Revision en2, by Medo., 2017-10-13 00:05:41

Hello!

I was recently solving this problem : http://poj.org/problem?id=1823

The problem basically says given an array of maximum size of 16000 where each element is one or zero, we need to perform the following two operations.

-Set range [L,R] to ones or zeros.

-Query maximum length of a subarray of ones

The problem can be indeed be solved by a segment tree, however using bitset we can do updates in O(N/32), and with N being 16000 that's just 500.

The problem is in querying the maximum length, I haven't reached any solution better than N operations, are the any ways to achieve something like N/32 ?

Please note, I already know the segment tree solution, I'm interested in bitset.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English Medo. 2017-10-13 00:10:38 2 Tiny change: 's, are the any ways' -> 's, are there any ways'
en2 English Medo. 2017-10-13 00:05:41 319 (published)
en1 English Medo. 2017-10-12 22:50:35 813 Initial revision (saved to drafts)