Counting Minimums with Segment Tree

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

1. Update index $i$ to value $v$
2. 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

Copy
const int MAXN = 2e5;

struct Node {
	int val = INT32_MAX, cnt = 1;
} tree[2 * MAXN];

// combines two segment tree nodes
Node merge(Node a, Node b) {
	if (a.val < b.val) {
		return a;

Solution - Area of Rectangles

Implementation

Copy
#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 bound
	bool operator<(const Event &e) { return x < e.x; }

Problems