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 there any ways to achieve something like N/32 ?
Please note, I already know the segment tree solution, I'm interested in bitset.
'Something like N/32' solution (O(N/20) — slower than O(N/32) but can be enough): just precalculate same values like in SegmentTree solution (if we have same solutions it is count ones on the prefix, suffix, and max count consecutive ones) for each of 2^20 mask, so further calculation is simple — just iterates over each 20 bits, and merge previous segment with len 20 with current, and pick the best.
Also this is nice, it still gets TLE. :) I'm starting to think either problem just requires fast updates so something like 500 per query is not sufficient, or maybe I can't implement it efficiently.
You can consult this wonderful post: Link
It explains quite nicely different ways to use bitset.
Thank you, I found it quite useful.
On a serious note, are the optimizations mentioned in the link legit?
Yes?!
Is that floyd's optimization really possible ? The O(n^2) one.
No, only Floydsss's.
I think I can help you with this question, my friend.
I see you are new in the fields of bitset optimizations — your optimization is very nice but has a lot of room for improvement. I will demonstrate to you now how you will be able to handle updates in O(N/(N-log(N))) time with some simple bitset usage.
1) Gather all ones from the initial array into a bitset.
2) Do the same with the zeros, but this time store them separately.
3) Merge the two bitsets from steps 1 and 2, creating in this way something very similar to a Fenwick tree, as you can see.
4) Divide the tree into components in which you can perform simple Fenwick tree operations, but instead of updating the actual values, you will be creating new bitsets to fill up the spaces of the logarithmic jumps.
Now you can see how you can simply answer queries in O(N/(N-log(N))) time as mentioned above.
We can add 2D fft with points (black, white) and get O(N/(N-log(N)/log(N)/log(N))
Thank you. Got AC.
BTW if you use 3D logarithmic bitset in #1 you can drop complexity to O(N/(N-1.678))
Hi, I know I am late , but I was solving this problem all I could think of was a O(P *sqrt(N)) solution ( sqrt decomposition)...
Can you tell me what your segment tree approach was?! I can seem to get a segment tree solution
Sorry, nevermind , solved it now!