Has Not Appeared

0/6

# Counting Minimums with Segment Tree

Authors: Benjamin Qi, Dustin Miao

Querying for the minimum and number of occurences of minimum in a range

### Prerequisites

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

Resources | ||||
---|---|---|---|---|

cp-algo |

We would like a data structure that can efficiently handle two types of operations:

- Update index $i$ to value $v$
- Report the minimum and the number of occurences of the minimum on a range $[l, r]$

We can use a normal segment tree to handle range queries, but slightly modify each node and the merge operation. Let each node be a pair of values $(\texttt{val}, \texttt{cnt})$, where $\texttt{val}$ is the minimum value and $\texttt{cnt}$ is the number occurences of the minimum value.

If node $c$ has two children $a$ and $b$, then

- if $a.\texttt{val} < b.\texttt{val}$, then $c = a$
- if $a.\texttt{val} > b.\texttt{val}$, then $c = b$
- if $a.\texttt{val} = b.\texttt{val}$, then $c = \{a.\texttt{val}, a.\texttt{cnt} + b.\texttt{cnt}\}$

### Implementation

C++

const int MAXN = 2e5;struct Node {int val = INT32_MAX, cnt = 1;} tree[2 * MAXN];// combines two segment tree nodesNode merge(Node a, Node b) {if (a.val < b.val) {return a;

### Solution - Area of Rectangles

Hint 1

Hint 2

Solution

### Implementation

C++

#include <bits/stdc++.h>using namespace std;const int MAXX = 1e6;const int MAXN = 2 * MAXX + 1;struct Event {int t, x, y0, y1;// t = 1 for left bound, -1 for right boundbool operator<(const Event &e) { return x < e.x; }

## Problems

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

CF | Easy | ## Show TagsDP | |||

mBIT | Normal | ||||

IOI | Hard | ||||

HR | Hard | ## Show TagsLazy SegTree | |||

CF | Very Hard |

### Optional: Permutation Tree

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