Perhaps today and/or tomorrow due to a power outage there may be disruptions in the work of Codeforces and Polygon. Please do not plan any important events during this time. If there are details or the exact time, we will definitely publish them. Estimated time of maintenance: from 2 Aug, 16:00 (UTC) to 2 Aug, 20:00 (UTC). ×

Taha1506's blog

By Taha1506, history, 6 weeks ago, In English

I was looking at the segment tree template of tourist. It doesn't have any operation for find the k'th zero or k'th one. So I wondered if is it possible to the with the current template without changing it. My question is : Is it possible to use find last and find first operations to find the k'th zero or one? I mean just using the current template to answer that kind of queries.Any ideas? If not what is the best ways to implement it for the current template so that we don't have to change the code a lot each time.

You can see the template of tourist here .

 
 
 
 
  • Vote: I like it
  • +1
  • Vote: I do not like it

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

You would need to keep the number of zeros/ones in each node, and then you can find the first prefix s.t. there are >=k zeros/ones.