# Max Suffix Query with Insertions Only

Author: Benjamin Qi

### Prerequisites

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:

- Add a pair $(a,b)$.
- For any $x$, query the maximum value of $b$ over all pairs satisfying $a≥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≤c$ and $b≤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}),…,(a_{k},b_{k})$ that we store in the map will satisfy $a_{1}<a_{2}<⋯<a_{k}$ and $b_{1}>b_{2}>⋯>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}≥x$. - When adding a pair $(a_{′},b_{′})$, first check if there exists $(a,b)$ already in the map such that $a≥a_{′},b≥b_{′}$.
- If so, then do nothing.
- Otherwise, insert $(a_{′},b_{′})$ into the map and repeatedly delete pairs $(a,b)$ such that $a≤a_{′},b≤b_{′}$ from the map until none remain.

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

### Implementation

C++

#define lb lower_boundmap<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

Status | Source | Problem Name | Difficulty | Tags | Solution | URL |
---|---|---|---|---|---|---|

CSES | Easy | View Solution | ||||

Plat | Hard | External Sol | ||||

CF | Very Hard | Check CF | ||||

CF | Very Hard | Check CF | ||||

CF | Very Hard | Check 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.