I have a problem that reduces to doing 2 kinds of queries:
- Add a number in $$${1,-1}$$$ to a range.
- Query the number of 0s in a suffix. It's guranteed that the array is nonnegative.
Constraints: $$$n\leq 10^5, Q\leq 192\cdot10^5$$$. My best solution did this problem in about 3.5 seconds using sqrt decomposition.
Solve with segment tree.
You need to maintain the minimum and the number of the minimnum in every vertex's subtree.
Bro, note that $$$Q\le 2\times10^7$$$
hi yoshi!!
i think youre trying to solve prob 2 from the recent trai he hung vuong
heres my solution: construct a lazy segment tree that for each node that represents the range (l -> r), the node will store the minimum element and its frequency in the range.
if the current minimum element in a range is 0, then we already have the corresponding answer. else there would be no zeros because the minimum element is > 0.
this way we could query/update in o(logn).
The input is incredibly large and I doubt if your constraint on $$$Q$$$ is wrong.
It's not out of the question if input and output are given in a compressed format to avoid IO issues (example: 1633E - Spanning Tree Queries)
bro really loves sqrt decomposition
Problem name??