Consultas de rango con línea de barrido

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	CSES	Intersection Points	Fácil	PURS	en el módulo

Solución - Intersection Points

Podemos barrer de abajo hacia arriba (por la coordenada $y$ ); almacenando dos eventos para segmentos verticales (uno para el inicio y uno para el final) y un evento para segmentos horizontales.

Podemos usar un Árbol de Fenwick para almacenar la cantidad de segmentos verticales activos para cada coordenada $x$ .

Luego, cada vez que encontramos el inicio de un segmento vertical, incrementamos el contador de $x$ en el BIT.

De forma análoga, decrementamos el contador de $x$ cada vez que vemos el final de un segmento vertical.

Cuando encontramos un segmento horizontal, consultaríamos la cantidad de rangos activos en $[x_1, x_2]$ donde $x_1$ es la coordenada $x$ menor y $x_2$ es la coordenada $x$ mayor del segmento.

Nuestra respuesta sería la suma de todas las consultas.

Implementación

Complejidad temporal: $\mathcal{O}(N\log N)$

C++Java


#include <bits/stdc++.h>
using namespace std;
 
 
// BeginCodeSnip{BIT (from the PURS module)}
template <class T> class BIT {
  private:
	int size;
	vector<T> bit;
	vector<T> arr;
 
  public:
	BIT(int size) : size(size), bit(size + 1), arr(size) {}
 
	void set(int ind, T val) { add(ind, val - arr[ind]); }
 
	void add(int ind, T val) {
		arr[ind] += val;
		ind++;
		for (; ind <= size; ind += ind & -ind) { bit[ind] += val; }
	}
 
	T pref_sum(int ind) {
		ind++;
		T total = 0;
		for (; ind > 0; ind -= ind & -ind) { total += bit[ind]; }
		return total;
	}
};
// EndCodeSnip
 
const int MAX_POS = 1e6;
 
int main() {
	int n;
	cin >> n;
 
	/*
	 * types of events (order for if some y values are equal):
	 * 1 -> start of vertical segment
	 * 2 -> horizontal segment
	 * 3 -> end of vertical segment
	 */
	vector<array<int, 4>> v;
	for (int i = 0, x1, y1, x2, y2; i < n; ++i) {
		cin >> x1 >> y1 >> x2 >> y2;
		if (y1 == y2) v.push_back({y1, 2, x1, x2});
		else {
			v.push_back({y1, 1, x1, 1});
			v.push_back({y2, 3, x1, 1});
		}
	}
	sort(begin(v), end(v));
 
	BIT<int> bit(2 * MAX_POS + 1);
	long long ans = 0;
	for (auto [y, type, x1, x2] : v) {
		x1 += MAX_POS;
		x2 += MAX_POS;
		if (type == 1) {
			bit.add(x1, 1);
		} else if (type == 2) {
			ans += bit.pref_sum(x2) - bit.pref_sum(x1 - 1);
		} else {
			bit.add(x1, -1);
		}
	}
 
	cout << ans << endl;
}


import java.io.*;
import java.util.*;
 
public class IntersectionPoints {
	// BeginCodeSnip{BIT (from the PURS module)}
	static class BIT {
		private int size;
		private int[] bit;
		private int[] arr;
 
		public BIT(int size) {
			this.size = size;
			this.bit = new int[size + 1];
			this.arr = new int[size];
		}
 
		public void set(int ind, int val) { add(ind, val - arr[ind]); }
 
		public void add(int ind, int val) {
			arr[ind] += val;
			ind++;
			for (; ind <= size; ind += ind & -ind) { bit[ind] += val; }
		}
 
		public int prefSum(int ind) {
			ind++;
			int total = 0;
			for (; ind > 0; ind -= ind & -ind) { total += bit[ind]; }
			return total;
		}
	}
	// EndCodeSnip
 
	private static final int MAX_POS = 1_000_000;
 
	static class Event implements Comparable<Event> {
		int y, type, x1, x2;
 
		public Event(int y, int type, int x1, int x2) {
			this.y = y;
			this.type = type;  // 1: start vert, 2: horiz, 3: end vert
			this.x1 = x1;
			this.x2 = x2;
		}
 
		@Override
		public int compareTo(Event other) {
			if (this.y != other.y) return Integer.compare(this.y, other.y);
			return Integer.compare(this.type, other.type);
		}
	}
 
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
 
		List<Event> events = new ArrayList<>();
		for (int i = 0; i < n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int x1 = Integer.parseInt(st.nextToken());
			int y1 = Integer.parseInt(st.nextToken());
			int x2 = Integer.parseInt(st.nextToken());
			int y2 = Integer.parseInt(st.nextToken());
 
			if (y1 == y2) {  // Horizontal
				events.add(new Event(y1, 2, x1, x2));
			} else {  // Vertical
				events.add(new Event(y1, 1, x1, 1));
				events.add(new Event(y2, 3, x1, 1));
			}
		}
		Collections.sort(events);
 
		BIT bit = new BIT(2 * MAX_POS + 1);
		long ans = 0;
 
		for (Event e : events) {
			int x1 = e.x1 + MAX_POS;
			int x2 = e.x2 + MAX_POS;
 
			if (e.type == 1) {
				bit.add(x1, 1);
			} else if (e.type == 2) {
				ans += bit.prefSum(x2) - bit.prefSum(x1 - 1);
			} else {
				bit.add(x1, -1);
			}
		}
 
		System.out.println(ans);
	}
}

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	Gold	Springboards	Normal	PURQ	—

Solución - Springboards

DP naive: $\mathcal{O}(P^2)$

El primer paso es crear una DP para resolver la primera subtarea. Los estados son los trampolines y las transiciones son entre trampolines. Primero, ordenar los trampolines por el par $(x_1, y_1)$ en orden creciente. Se puede mostrar que para todo $i$ , $j$ , donde $i < j$ , Bessie no puede usar el trampolín $j$ y luego el $i$ .

Para cada trampolín $i$ , sea $\texttt{ans}[i]$ la distancia mínima que hay que caminar hasta el punto de inicio del trampolín $i$ .

Sea $\texttt{dist}(a, b)$ la distancia caminando desde el final del trampolín $a$ hasta el inicio del trampolín $b$ .

\texttt{dist}(a, b) = x_1[b] + y_1[b] - x_2[a] - y_2[a]

Entonces, las transiciones son:

\texttt{ans}[i] = \min\limits_{j < i, x_2[j] \le x_1[i], y_2[j] \le y_1[i]}(\texttt{ans}[j] + \texttt{dist}(j, i))

Solución completa: $\mathcal{O}(P \log P)$

Optimizar la DP involucra el uso de un árbol de segmentos de actualización puntual de mínimo y consulta de rango. Primero expandamos $dist(i, j)$ en la fórmula de transición.

\texttt{ans}[i] = \min\limits_{j < i, x_2[j] \le x_1[i], y_2[j] \le y_1[i]}(\texttt{ans}[j] + x_1[i] + y_1[i] - x_2[j] - y_2[j])

\texttt{ans}[i] = x_1[i] + y_1[i] + \min\limits_{j < i, x_2[j] \le x_1[i], y_2[j] \le y_1[i]}(\texttt{ans}[j] - x_2[j] - y_2[j])

Notamos que todo lo que está dentro del $\min$ solo depende de $j$ . El árbol de segmentos almacena $\texttt{ans}[j] - x_2[j] - y_2[j]$ en el índice $y_2[j]$ . Podemos separar el inicio y el final de los trampolines para crear dos eventos distintos por trampolín, ordenando todavía por $(x, y)$ . Cuando el evento es el inicio de un trampolín, actualizamos $ans[i]$ mediante una consulta al árbol de segmentos. Cuando el evento es el final de un trampolín, actualizamos el árbol de segmentos.

Al procesar en orden, las dos primeras condiciones del $\min$ siempre se cumplen. La tercera es donde entra el árbol de segmentos: consultar el rango $[0, y_1[i]]$ basta para satisfacer todas las restricciones.

Debido al $N$ grande, se requiere compresión de coordenadas en el código.

Implementación

Complejidad temporal: $\mathcal{O}(P \log P)$

C++Java


#include <bits/stdc++.h>
using namespace std;
 
// BeginCodeSnip{Segment Tree (from the PURS module)}
template <class T> class MinSegmentTree {
  private:
	const T DEFAULT = std::numeric_limits<T>().max();
 
	vector<T> segtree;
	int len;
 
  public:
	MinSegmentTree(int len) : len(len), segtree(len * 2, DEFAULT) {}
 
	void set(int ind, T val) {
		ind += len;
		segtree[ind] = min(segtree[ind], val);
		for (; ind > 1; ind /= 2) {
			segtree[ind / 2] = std::min(segtree[ind], segtree[ind ^ 1]);
		}
	}
 
	T range_min(int start, int end) {
		T min = DEFAULT;
		for (start += len, end += len; start < end; start /= 2, end /= 2) {
			if (start % 2 == 1) { min = std::min(min, segtree[start++]); }
			if (end % 2 == 1) { min = std::min(min, segtree[--end]); }
		}
		return min;
	}
};
// EndCodeSnip
 
struct Point {
	int x, y;
	int i;
	bool is_start;
 
	Point(int x, int y, int i, bool is_start) : x(x), y(y), i(i), is_start(is_start) {}
 
	bool operator<(const Point &p) {
		if (x == p.x) { return y < p.y; }
		return x < p.x;
	}
};
 
vector<int> distinct_y;
 
int y_index(int y) {
	return lower_bound(begin(distinct_y), end(distinct_y), y) - begin(distinct_y);
}
 
int main() {
	freopen("boards.in", "r", stdin);
	int n, p;
	cin >> n >> p;
 
	vector<Point> events;
	for (int i = 0; i < p; ++i) {
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		events.emplace_back(x1, y1, i, true);   // start point
		events.emplace_back(x2, y2, i, false);  // end point
		distinct_y.push_back(y1);
		distinct_y.push_back(y2);
	}
 
	sort(begin(distinct_y), end(distinct_y));
	sort(begin(events), end(events));
 
	vector<int> ans(p);
	MinSegmentTree<int> segtree(2 * p);
	segtree.set(0, 0);
	for (const Point &p : events) {
		if (p.is_start) {
			ans[p.i] = p.x + p.y + segtree.range_min(0, y_index(p.y) + 1);
		} else {
			segtree.set(y_index(p.y), ans[p.i] - p.x - p.y);
		}
	}
 
	freopen("boards.out", "w", stdout);
	// adds 2N to include the transition
	// from the last springboard to the endpoint
	cout << segtree.range_min(0, 2 * p) + 2 * n;
}


import java.io.*;
import java.util.*;
 
public class Springboards {
	// BeginCodeSnip{Segment Tree (from the PURS module)}
	static class MinSegmentTree {
		private int len;
		private int[] segtree;
		private final int DEFAULT = Integer.MAX_VALUE;
 
		public MinSegmentTree(int len) {
			this.len = len;
			segtree = new int[len * 2];
			Arrays.fill(segtree, DEFAULT);
		}
 
		public void set(int ind, int val) {
			ind += len;
			segtree[ind] = Math.min(segtree[ind], val);
			for (; ind > 1; ind /= 2) {
				segtree[ind / 2] = Math.min(segtree[ind], segtree[ind ^ 1]);
			}
		}
 
		public int rangeMin(int start, int end) {
			int min = DEFAULT;
			for (start += len, end += len; start < end; start /= 2, end /= 2) {
				if (start % 2 == 1) min = Math.min(min, segtree[start++]);
				if (end % 2 == 1) min = Math.min(min, segtree[--end]);
			}
			return min;
		}
	}
	// EndCodeSnip
 
	static class Point implements Comparable<Point> {
		int x, y, i;
		boolean isStart;
 
		public Point(int x, int y, int i, boolean isStart) {
			this.x = x;
			this.y = y;
			this.i = i;
			this.isStart = isStart;
		}
 
		@Override
		public int compareTo(Point p) {
			if (this.x != p.x) return Integer.compare(this.x, p.x);
			return Integer.compare(this.y, p.y);
		}
	}
 
	static List<Integer> distinctY = new ArrayList<>();
 
	static int yIndex(int y) {
		int idx = Collections.binarySearch(distinctY, y);
		return idx < 0 ? -1 : idx;
	}
 
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new FileReader("boards.in"));
		PrintWriter pw = new PrintWriter(new FileWriter("boards.out"));
		StringTokenizer st = new StringTokenizer(br.readLine());
 
		int n = Integer.parseInt(st.nextToken());
		int p = Integer.parseInt(st.nextToken());
 
		List<Point> events = new ArrayList<>();
		for (int i = 0; i < p; ++i) {
			st = new StringTokenizer(br.readLine());
			int x1 = Integer.parseInt(st.nextToken());
			int y1 = Integer.parseInt(st.nextToken());
			int x2 = Integer.parseInt(st.nextToken());
			int y2 = Integer.parseInt(st.nextToken());
 
			events.add(new Point(x1, y1, i, true));
			events.add(new Point(x2, y2, i, false));
			distinctY.add(y1);
			distinctY.add(y2);
		}
 
		Collections.sort(distinctY);
		// Remove duplicates for coordinate compression
		List<Integer> uniqueY = new ArrayList<>();
		if (!distinctY.isEmpty()) {
			uniqueY.add(distinctY.get(0));
			for (int i = 1; i < distinctY.size(); i++) {
				if (!distinctY.get(i).equals(distinctY.get(i - 1))) {
					uniqueY.add(distinctY.get(i));
				}
			}
		}
		distinctY = uniqueY;
 
		Collections.sort(events);
 
		int[] ans = new int[p];
		MinSegmentTree segtree = new MinSegmentTree(distinctY.size() + 1);
		segtree.set(0, 0);
 
		for (Point point : events) {
			int yIdx = yIndex(point.y);
			if (point.isStart) {
				int query = segtree.rangeMin(0, yIdx + 1);
				ans[point.i] = point.x + point.y + query;
			} else {
				segtree.set(yIdx, ans[point.i] - point.x - point.y);
			}
		}
 
		// Query the full range to account for the transition from the last springboard
		// to (N, N) rangeMin returns min(ans[j] - x2[j] - y2[j]). We add 2*N to
		// complete the formula.
		pw.println(segtree.rangeMin(0, distinctY.size() + 1) + 2L * n);
		pw.close();
		br.close();
	}
}

Enfoque alternativo

Resulta que también hay un método más simple, aunque menos directo, para resolver este problema.

El problema se reduce a tener una estructura de datos que soporte las siguientes operaciones:

Agregar un par $(a,b)$ .
Para cualquier $x$ , consultar el valor mínimo de $b$ sobre todos los pares que satisfacen $a\le x$ .

Esta solución se describe en el editorial oficial y en el otro módulo.

Problemas

Fuente	Nombre	Dificultad	Tags	Solución
HE	Twin Permutations	Fácil	PURS	Solución
Platinum	Slingshot	Normal	PURQ	Solución
Platinum	Load Balancing	Normal		Solución
CSES	Robot Path	Difícil	PURQ	—
IZhO	2019 - Hedgehog Daniyar and Algorithms	Difícil	Stack, PURQ, Lazy SegTree	Solución

Problemas de LIS

Fuente	Nombre	Dificultad	Tags	Solución
Balkan OI	★ 2011 - Trapezoid	Difícil	DP, PURS	Solución
COCI	★ 2016 - Zoltan	Difícil	DP, PURS	Solución
Platinum	Sort It Out	Muy difícil	DP	—