Max Suffix Query with Insertions Only

Author: Benjamin Qi

A solution to USACO Gold - Springboards.

Table of Contents


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

Focus Problem – try your best to solve this problem before continuing!

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

  1. Add a pair (a,b)(a,b).
  2. For any xx, query the maximum value of bb over all pairs satisfying axa\ge x.

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 (a,b)(a,b) and (c,d)(c,d) in the map such that aca\le c and bdb\le d, we can simply ignore (a,b)(a,b) (and the answers to future queries will not be affected). So at every point in time, the pairs (a1,b1),(a2,b2),,(ak,bk)(a_1,b_1),(a_2,b_2),\ldots,(a_k,b_k) that we store in the map will satisfy a1<a2<<aka_1 < a_2 < \cdots < a_k and b1>b2>>bkb_1 > b_2 > \cdots > b_k.

  • Querying for a certain xx can be done with a single lower_bound operation, as we just want the minimum ii such that aixa_i\ge x.
  • When adding a pair (a,b)(a',b'), first check if there exists (a,b)(a,b) already in the map such that aa,bba\ge a', b\ge b'.
    • If so, then do nothing.
    • Otherwise, insert (a,b)(a',b') into the map and repeatedly delete pairs (a,b)(a,b) such that aa,bba\le a', b\le b' from the map until none remain.

If there are NN insertions, then each query takes O(logN)\mathcal{O}(\log N) time and adding a pair takes O(logN)\mathcal{O}(\log N) time amortized.



#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.


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


StatusSourceProblem NameDifficultyTags
Show TagsPURQ
Show TagsPURQ
CFVery Hard
Show TagsPURQ
CFVery Hard
Show TagsPURQ
CFVery Hard
Show TagsPURQ

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!