Cómo resolver este problema usando la descomposición de raíz cuadrada La tecnología cambia la vida futura

Cómo resolver este problema usando la descomposición de raíz cuadrada

Divida los bordes en bloques de [math] \ sqrt {n} [/ math]. Luego, puede responder la consulta para cualquier subrango de estos bloques, de los cuales hay [math] \ textstyle {{\ sqrt {n} \ choose 2}} \ aprox n / 2 [/ math]. Esto lleva [math] \ sqrt {n} [/ math] tiempo para cada una de estas subranges, ya que debe agregar un bloque al final de una subranga computada anterior para obtener una nueva subranga, por lo que en total esto toma [math] O (n \ sqrt {n}) [/ math] operaciones.

Luego, tendrá que procesar cada una de las consultas reales sin conexión. Eso significa que tendrá que leerlos todos, distribuirlos por cuál de estos subrangos se encuentran, es decir, tomar el techo del lado izquierdo y el piso del lado derecho, y luego responderlos mientras calcula estos subrangos de bloque. Para responder a cada consulta, debe agregar hasta [math] \ sqrt {n} [/ math] elementos a la izquierda y a la derecha del subrango de bloques previamente calculado. Una vez que la consulta ha sido respondida, reinicie y continúe con la siguiente consulta. El algoritmo total toma [matemática] O \ left (\ alpha (n) (n + q) \ sqrt {n} \ right) [/ math] tiempo, donde q es el número de consultas y [math] \ alpha [ / math] es la función inversa de Ackermann, que surge del uso de la estructura de datos de Disjoint-set para contar componentes.

Esta solución no es trivial para el código, ya que implica un procesamiento fuera de línea extraño y restablecer el conjunto disjunto, pero es conceptualmente más fácil que la solución alternativa de árbol de corte de enlace. Si te ayuda, puedes ver mi solución para 86D – Codeforces, que es similar.