I recently came across a problem which reduced to the following:-
Initially, we are provided a number line. Every second, we are being given one of the following two kind of commands
- add(L,R) : If we receive this command, we have to place a stick in the interval [L,R].
- remove(L,R) : We receive this command only if we received add(L,R) in an earlier time. Remove a stick [L,R] added earlier
After every second, we have to tell the total merged length. In a merged length, we count the overlap length of two or more sticks only once. For example if [1,5] and [4,7] sticks were placed, their mergal is [1,7] and mergal length 6. It would be great if someone can help me approach the problem.
Auto comment: topic has been updated by bitch_house (previous revision, new revision, compare).
We can solve this with a lazy segment tree.
Essentially we are given 3 queries: add 1 to [L,R], subtract 1 from [L,R], count number of nonzero elements in the array.
Note that the value at any index will never go below 0 (you cannot have a negative number of sticks that cover a position). Therefore it suffices to maintain (minimum in range, frequency of minimum) in each node of the segment tree, which can then be used to count the number of 0s in the array. Subtracting this value from the total length of the array is the answer to the query.
If the bounds on L and R are too large, we can use a sparse segment tree or careful coordinate compression.
You can do it with a lazy segtree. Define the
cntvalue of a point as the number of intervals covering that point. In each node you keep track of the minimumcntvalue in the range and the number of points with the minimumcntvalue. If the coordinates are too large, use coordinate compression and keep the distance between compressed points.