Editorial for Inversiones en Rango

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: aniervs

Subtarea 1

$a = b$ ~a = b~ y $c = d$ ~c = d~

Solo hay que saber si $p_a > p_b$ ~p_a > p_b~.

Subtarea 2

$p_i < p_{i-1}\ \forall i \in [2, n]$ ~p_i < p_{i-1}\ \forall i \in [2, n]~

Tenemos que $p_x > p_y$ ~p_x > p_y~ para cada par $(x, y)$ ~(x, y)~ con $x \in [a, b]$ ~x \in [a, b]~ y $y \in [c, d]$ ~y \in [c, d]~. Por tanto, la respuesta es $(b - a + 1) \cdot (d - c + 1)$ ~(b - a + 1) \cdot (d - c + 1)~.

Subtarea 3

$n, q \le 300$ ~n, q \le 300~

En esta subtarea, podemos probar todos los pares $(x, y)$ ~(x, y)~ con $x \in [a, b]$ ~x \in [a, b]~ y $y \in [c, d]$ ~y \in [c, d]~. Cada uno de esos rangos tiene longitud $\mathcal{O}(n)$ ~\mathcal{O}(n)~, por lo que esta solución tiene complejidad temporal $\mathcal{O}(q\cdot n^2)$ ~\mathcal{O}(q\cdot n^2)~.

Para las próximas subtareas, primeramente computaremos todos los pares $(x, y)$ ~(x, y)~ con $x > y$ ~x > y~ y $p_x > p_y$ ~p_x > p_y~. Llamemos a esos pares como puntos relevantes.

Subtarea 4

$q \le 6000$ ~q \le 6000~

Digamos $cnt(x, b)$ ~cnt(x, b)~ es la cantidad de puntos relevantes $(x, y)$ ~(x, y)~ con $y \le b$ ~y \le b~.

Entonces, la respuesta a una pregunta $([a, b], [c, d])$ ~([a, b], [c, d])~ es

$\displaystyle\sum_{x \in [a, b]} (cnt(x, d) - cnt(x, c - 1))$

Podemos computar $cnt(x, ?)$ ~cnt(x, ?)~ en tiempo $\mathcal{O}(n)$ ~\mathcal{O}(n)~:

$cnt(x, y) = cnt(x, y - 1) + [\ (x, y) \text{ es relevante }]$ .

De esa manera, se puede responder cada pregunta en tiempo $\mathcal{O}(n)$ ~\mathcal{O}(n)~, quedando en $\mathcal{O}(q \cdot n)$ ~\mathcal{O}(q \cdot n)~.

Subtarea 5

Similar a la subtarea 6, pero aceptando soluciones subóptimas, como un $O((n^2+q)\log{n}))$ ~O((n^2+q)\log{n}))~ debido al uso de alguna estructura de datos logarítmica.

Subtarea 6

Podemos extender la idea de computar la cantidad de puntos con $y \le T$ ~y \le T~ para ambas coordenadas. Digamos que $s(a, b)$ ~s(a, b)~ es la cantidad de puntos relevantes $(x,y)$ ~(x,y)~ con $x \le a; y \le b$ ~x \le a; y \le b~.

Hay varias formas de computar $s(?,?)$ ~s(?,?)~ en tiempo $\mathcal{O}(n^2)$ ~\mathcal{O}(n^2)~.

Una forma, es usando $cnt(?,?)$ ~cnt(?,?)~ de la subtarea anterior. Podemos decir que $s(a, b) = \displaystyle\sum_{x \le a} cnt(x, b)$ . Y, naturalmente, podemos computar $s(a,b)$ ~s(a,b)~ a partir de valores ya computados: $s(a,b) = s(a-1,b) + cnt(a,b)$ ~s(a,b) = s(a-1,b) + cnt(a,b)~.
Otra forma muy conocida, es: $s(a,b) = s(a-1,b) + s(a,b-1) - s(a-1,b-1) + [(a,b) es relevante]$ .

Entonces, la respuesta a una pregunta $([a, b], [c, d])$ ~([a, b], [c, d])~ es

$s(c, d) - s(c,b-1) - s(a-1,d) + s(a-1,b-1)$

Así, podemos responder cada pregunta en tiempo constante, obteniendo complejidad final $\mathcal{O}(n^2 + q)$ ~\mathcal{O}(n^2 + q)~.

Comments

There are no comments at the moment.