Asumiendo revolver {Axe, …, Ay-1, Ay} significa que se convierte en, {Ay, Axe, …, Ay-1}
Primer paso, encontraremos dónde terminará el primer elemento de la secuencia Ax después de la operación. Se puede hacer fácilmente con [math] pos = [/ math] [math] x + T mod (y-x + 1) [/ math]
Luego necesitamos encontrar cuántos elementos del frente se moverán hacia atrás. Para esto podemos encontrar el rango [math] nr [/ math] [math] = y – pos + 1 [/ math]
- ¿Cómo obtenemos ideas para resolver preguntas de programación dinámica?
- ¿Existe un algoritmo de tiempo O (N) para esta pregunta?
- ¿Qué libro sobre algoritmos es una lectura obligada para un programador?
- ¿Cuál es la diferencia entre un código y un algoritmo?
- Cómo resolver SPOJ.com - Problema GERGOVIA en SPOJ
Ahora, sabemos que la secuencia {Ax, …, Ay-1, Ay} se verá como {Ax + nr, Ax + nr + 1, …, Ax, Ax + 1, …, Ax + nr-1} después del operación giratoria.
Todo lo que queda es dividir y fusionar según sea necesario.
Suponiendo que el árbol inicial se denota por root. Tenemos,
- división (raíz, l, r, y)
- división (l, l1, r1, x-1)
- split (r1, l2, r2, nr-1) // nr indica el número de elementos de la parte frontal que deben desplazarse hacia la parte posterior, por lo que (nr-1) indica el índice
- merge (r1, r2, l2) // r2 se convierte en izquierda y l2 se convierte en derecha para realizar la operación de revolución.
- fusionar (l, l1, r1)
- fusionar (raíz, l, r)
¡Espero eso ayude! ¡Buena suerte!
