Rare
0/6

# Max Suffix Query with Insertions Only

Author: Benjamin Qi

### Prerequisites

A solution to USACO Gold - Springboards.

ImplementationProblems
Edit on Github

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)$.
2. For any $x$, query the maximum value of $b$ over all pairs satisfying $a\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)$ and $(c,d)$ in the map such that $a\le c$ and $b\le d$, we can simply ignore $(a,b)$ (and the answers to future queries will not be affected). So at every point in time, the pairs $(a_1,b_1),(a_2,b_2),\ldots,(a_k,b_k)$ that we store in the map will satisfy $a_1 < a_2 < \cdots < a_k$ and $b_1 > b_2 > \cdots > b_k$.

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

If there are $N$ insertions, then each query takes $O(\log N)$ time and adding a pair takes $O(\log N)$ time amortized.

### Implementation

C++

1#define lb lower_bound2
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