J. Leveling Ground
Author: Suhendry Effendy.
Prepared by: Suhendry Effendy, Felix Halim.
Problem: J – Leveling Ground
First, notice that for each segment [L, R], all surfaces shape (/, \, _) on [L, R] will be disposed. By first computing the partial sum on the cost to remove each surface, we can answer any [L, R] query in O(1) – note: this is only for the surface.
The real challange is: how to compute the number of disposed full land for each [L, R] query? It’s not hard to arrive at O(lg n) solution (e.g., by modifying priority queue), but it’s not enough for this problem; we need an O(1) solution. Specifically, we need a data structure which can:
- push an item,
- pop the oldest item (queue order: first in first out),
- answer a query of the lowest element in the data structure.
All those queries should be accomplished in O(1).
One simple way is to maintain two data structures: a queue (Q) and a deque (D). The queue is used to handle the 1st and 2nd queries (push and pop), while we can use deque to handle the 3rd query.
D maintains non-decreasing elements with the last inserted element in Q presents in D. Whenever an element X is inserted into Q, pop-back all elements in D which are larger than X, and then push-back X into D. Those discarded elements will never be part of the answer for the lowest element query as X is lower than all those elements (so, there’s no point on keeping them). The most front element in D is the lowest element, so 3rd query can be answered in O(1). Upon popping an element from Q, check whether the removed element is the same as the front-most element in D, if so, then we should pop-front D (and the next element becomes the lowest element).