PrevNext
Rare
 0/6

Max Suffix Query with Insertions Only

Author: Benjamin Qi

A solution to USACO Gold - Springboards.

Note: This was originally in Gold, but the practice problems were too hard ...

Focus Problem – read through this problem before continuing!


To solve this problem, we need a data structure that supports operations similar to the following:

  1. Add a pair .
  2. For any , query the maximum value of over all pairs satisfying .

This can be solved with a segment tree, but a simpler option is to use a map. We rely on the fact that if there exist pairs and in the map such that and , we can simply ignore (and the answers to future queries will not be affected). So at every point in time, the pairs that we store in the map will satisfy and .

  • Querying for a certain can be done with a single lower_bound operation, as we just want the minimum such that .
  • When adding a pair , first check if there exists already in the map such that .
    • If so, then do nothing.
    • Otherwise, insert into the map and repeatedly delete pairs such that from the map until none remain.

If there are insertions, then each query takes time and adding a pair takes time amortized.

Implementation

C++

#define lb lower_bound
map<int,ll> m;
void ins(int a, ll b) {
auto it = m.lb(a); if (it != end(m) && it->s >= b) return;
it = m.insert(it,{a,b}); it->s = b;
while (it != begin(m) && prev(it)->s <= b) m.erase(prev(it));
}
ll query(int x) { auto it = m.lb(x);
return it == end(m) ? 0 : it->s; }
// it = end(m) means that no pair satisfies a >= x

You can check the analysis for the full solution to the original problem.

Warning!

"Maximum second element" should be "minimum second element" in the analysis.

Problems

StatusSourceProblem NameDifficultyTagsSolutionURL
CSESEasyView Solution
PlatHardExternal Sol
CFVery HardCheck CF
CFVery HardCheck CF
CFVery HardCheck CF

Module Progress:

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Give Us Feedback on Max Suffix Query with Insertions Only!

Leave suggestions for us by making a post on the USACO Forum! Ex: Unclear sections, mislabeled problems, etc.

PrevNext