Contar mínimos con Árbol de Segmentos

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	CSES	Area of Rectangles	Normal	Lazy SegTree	en el módulo

Recursos
Fuente	Recurso	Notas
cp-algo	Finding max and number of occurrences

Quisiéramos una estructura de datos que pueda manejar de forma eficiente dos tipos de operaciones:

Actualizar el índice $i$ al valor $v$
Reportar el mínimo y el número de ocurrencias del mínimo en un rango $[l, r]$

Podemos usar un Árbol de Segmentos normal para manejar consultas de rango, pero modificando ligeramente cada nodo y la operación de fusión. Sea cada nodo un par de valores $(\texttt{val}, \texttt{cnt})$ , donde $\texttt{val}$ es el valor mínimo y $\texttt{cnt}$ es el número de ocurrencias del valor mínimo.

Si el nodo $c$ tiene dos hijos $a$ y $b$ , entonces

si $a.\texttt{val} < b.\texttt{val}$ , entonces $c = a$
si $a.\texttt{val} > b.\texttt{val}$ , entonces $c = b$
si $a.\texttt{val} = b.\texttt{val}$ , entonces $c = \{a.\texttt{val}, a.\texttt{cnt} + b.\texttt{cnt}\}$

Implementación

C++


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;
	} else if (a.val > b.val) {
		return b;
	}
	return {a.val, a.cnt + b.cnt};
}
 
// updates the ith value to v
void update(int i, int v) {
	for (tree[i += MAXN] = {v, 1}; i > 1; i >>= 1) {
		tree[i >> 1] = merge(tree[i], tree[i ^ 1]);
	}
}
 
// returns the minimum and occurrences between indices l and r
Node query(int l, int r) {
	Node res;
	for (l += MAXN, r += MAXN + 1; l < r; l >>= 1, r >>= 1) {
		if (l & 1) res = merge(res, tree[l++]);
		if (r & 1) res = merge(res, tree[--r]);
	}
	return res;
}

Solución - Area of Rectangles

Pista 1

Contar el número de cuadrados que están cubiertos por ninguno de los rectángulos de entrada.

Pista 2

Ordenar los rectángulos por coordenada $x$ y correr una línea de barrido.

Podemos usar las técnicas introducidas en Consultas de rango con línea de barrido

Barrimos de izquierda a derecha sobre las coordenadas $x$ , manteniendo dos eventos por cada rectángulo: uno para el borde izquierdo y uno para el borde derecho. Mantenemos un Árbol de Segmentos perezoso sobre las coordenadas $y$ .

Cuando nos encontramos con un borde izquierdo de algún rectángulo con coordenadas $y$ $(y_0, y_1)$ , incrementamos cada índice $i \in [y_0, y_1]$ en 1
Cuando nos encontramos con un borde derecho de algún rectángulo con coordenadas $y$ $(y_0, y_1)$ , decrementamos cada índice $i \in [y_0, y_1]$ en 1

Luego, para cada $x$ , simplemente necesitamos contar el número de índices distintos de cero, que corresponden a índices cubiertos por al menos un rectángulo. ¿Cómo hacemos esto?

En lugar de contar el área cubierta por al menos un rectángulo, contemos la cantidad de espacio cubierto por ningún rectángulo. Podemos restar esta cantidad del número total de índices para obtener el valor que queremos.

Podemos usar un Árbol de Segmentos que cuenta el número de ocurrencias del valor mínimo. Como el valor mínimo es al menos cero (no puede haber un número negativo de rectángulos en una posición), el número de cuadrados no cubiertos es igual al número de cuadrados con valor 0.

Implementación

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 bound
	bool operator<(const Event &e) { return x < e.x; }
};
 
int N;
vector<Event> E;
 
// segment tree
pair<long long, long long> tree[MAXN * 4];
int lazy[MAXN * 4];
 
pair<long long, long long> merge(pair<long long, long long> a,
                                 pair<long long, long long> b) {
	if (a.first < b.first) { return a; }
	if (a.first > b.first) { return b; }
	return {a.first, a.second + b.second};
}
 
// pushes lazy updates down to children
void pushdown(int t) {
	if (lazy[t]) {
		tree[t << 1].first += lazy[t];
		lazy[t << 1] += lazy[t];
		tree[t << 1 | 1].first += lazy[t];
		lazy[t << 1 | 1] += lazy[t];
		lazy[t] = 0;
	}
}
 
// constructs the segment tree
void build(int t = 1, int tl = 0, int tr = MAXN) {
	if (tl == tr) {
		tree[t] = {0, 1};
		return;
	}
 
	int tm = (tl + tr) >> 1;
	build(t << 1, tl, tm);
	build(t << 1 | 1, tm + 1, tr);
	tree[t] = merge(tree[t << 1], tree[t << 1 | 1]);
}
 
// adds v to indices l to r
void update(int l, int r, int v, int t = 1, int tl = 0, int tr = MAXN) {
	if (r < tl || tr < l) { return; }
	if (l <= tl && tr <= r) {
		tree[t].first += v;
		lazy[t] += v;
		return;
	}
	pushdown(t);
 
	int tm = (tl + tr) >> 1;
	update(l, r, v, t << 1, tl, tm);
	update(l, r, v, t << 1 | 1, tm + 1, tr);
	tree[t] = merge(tree[t << 1], tree[t << 1 | 1]);
}
 
// queries min and count of entire segment tree
long long query() {
	// always maintain one element with value of zero
	// so we don't have to check if zero is the minimum
	return MAXN + 1 - tree[1].second;
}
 
int main() {
	cin >> N;
	build();
	for (int i = 0; i < N; i++) {
		int x0, y0, x1, y1;
		cin >> x0 >> y0 >> x1 >> y1;
 
		// make coordinates positive
		x0 += MAXX, y0 += MAXX;
		x1 += MAXX, y1 += MAXX;
 
		E.push_back({1, x0, y0, y1 - 1});
		E.push_back({-1, x1, y0, y1 - 1});
	}
 
	sort(E.begin(), E.end());
 
	long long ans = 0;
	update(E[0].y0, E[0].y1, 1);
	for (int i = 1; i < 2 * N; i++) {
		ans += query() * (E[i].x - E[i - 1].x);
		update(E[i].y0, E[i].y1, E[i].t);
	}
	cout << ans << '\n';
}

Problemas

Fuente	Nombre	Dificultad	Tags	Solución
CF	Culture Code	Fácil	DP	—
mBIT	Zookeepers' Gathering	Normal		—
IOI	2008 - Pyramid Base	Difícil		—
HR	Strange Tree	Difícil	Lazy SegTree	—
CF	Good Subsegments	Muy difícil		Solución

Árbol de permutación

Tutorial