bitch_house's blog

By bitch_house, history, 4 years ago, In English

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.

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

4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by bitch_house (previous revision, new revision, compare).

4 years ago, # |
Rev. 2   Vote: I like it +31 Vote: I do not like it

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.

4 years ago, # |
Rev. 4   Vote: I like it +8 Vote: I do not like it

You can do it with a lazy segtree. Define the cnt value of a point as the number of intervals covering that point. In each node you keep track of the minimum cnt value in the range and the number of points with the minimum cnt value. If the coordinates are too large, use coordinate compression and keep the distance between compressed points.