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 (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)O(\log N) time and adding a pair takes O(logN)O(\log N) time amortized.

Implementation

C++

1#define lb lower_bound
2
3map<int,ll> m;
4void ins(int a, ll b) {
5 auto it = m.lb(a); if (it != end(m) && it->s >= b) return;
6 it = m.insert(it,{a,b}); it->s = b;
7 while (it != begin(m) && prev(it)->s <= b) m.erase(prev(it));
8}
9ll query(int x) { auto it = m.lb(x);
10 return it == end(m) ? 0 : it->s; }

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 NameDifficultyTagsSolution
CSESEasyView Solution
PlatHardExternal Sol
CFVery HardCheck CF
CFVery HardCheck CF
CFVery HardCheck CF

Module Progress:

Give Us Feedback on Max Suffix Query with Insertions Only!

PrevNext