Subtarea 1:

Se puede mantener ~U~ y ~V~ en vectores, y en cada query, recorrer pares de elementos y quedarse con el mejor valor como se indica en el texto del problema.

Complejidad ~O(q^3)~

Subtarea 2:

Se puede hacer como en la subtarea 1, pero usando un multiset para soportar la eliminación de puntos, o hacerlo en tiempo lineal con el vector.

Complejidad ~O(q^3)~

Subtarea 3:

Se pueden mantener ~U~ y ~V~ como vectores, y mantener la mejor respuesta, cada vez que se inserte un nuevo elemento en ~U~, probarlo con todos los de ~V~ y actualizar la mejor respuesta si es necesario, similarmente en caso contrario.

Complejidad ~O(q^2)~

Subtarea 4:

Se pueden mantener las soluciones de todos los pares de elementos de ~U~ y ~V~ en una estructura de datos.

Al insertar un elemento en ~U~, insertar las respuestas de los pares formados por él y cada elemento de ~V~, similarmente al insertar en ~V~,

Al eliminar un elemento de ~U~ eliminar las respuestas de los pares formados por él y cada elemento de ~V~ similarmente al eliminar en ~V~.

Luego las queries son simplemente decir el mayor número de la estructura de datos.

Usando como estructura un multiset, la complejidad sería ~O(q^2\log{q^2})~ lo cual unido a la alta constante del multiset, podría ocasionar tiempo límite excedido.

Para optimizar se puede usar un sqrt descomposition que soporte updates en ~O(1)~ y queries en ~O(\sqrt{n})~ para lograr una complejidad de ~O(q^2+q\cdot\sqrt{n})~.

Subtarea 5:

En esta subtarea se puede mantener una pila monótona para ~U~ y otra para ~V~, y usar una idea similar a la de la subtarea 3 pero usando búsqueda binaria para optimizar las operaciones.

Subtarea 6:

Esta subtarea permite soluciones con complejidad ~O(n\cdot\sqrt{n})~ usando sqrt on queries, o sea, procesando cada bloque de tamaño ~O(\sqrt{n})~ de queries de forma independiente.

Subtarea 7:

Tenga en cuenta que decir ~u_x + v_x \ge u_y + v_y~ es equivalente a decir ~u_x - u_y \ge v_y - v_x~ .

Esto motiva a mantener ~u_x - u_y~ y ~v_y - v_x~ para los elementos en ~U~ y ~V~ respectivamente. Para cada elemento en ~U~ , llame a ~u_x - u_y~ su ~ID~, y para cada elemento en ~V~, llame a ~v_y - v_x~ su ~ID~. Cree un árbol de segmentos donde las hojas estén codificadas en ~ID~.

Cada nodo en el árbol de segmentos rastrea cinco valores, los valores mínimos posibles de ~u_x, u_y, v_x, v_y~ , y el valor mínimo posible de ~\max(u_x + v_x, u_y + v_y)~ sobre todos los puntos cubiertos por el rango de ~ID~ implícito. Los primeros cuatro valores se pueden mantener directamente, por lo que queda por mantener el quinto valor. Dado que ~u_x + v_x \ge u_y + v_y~ es equivalente a ~u_x - u_y \ge v_y - v_x~, para cualquier nodo interno, el mínimo posible el valor de ~\max(u_x + v_x, u_y + v_y)~ se obtiene sumando ~u_y~ del hijo izquierdo y ~v_y~ del derecho hijo, o sumando ~u_x~ del hijo derecho y ~v_x~ del hijo izquierdo. Por lo tanto, actualizar los valores para un nodo dado se puede hacer en tiempo constante, por lo que cada actualización se puede procesar en tiempo logarítmico.