Queries y LCPs

Points: 100 (partial)

Time limit: 2.5s

Memory limit: 256M

Author:

Problem type

Allowed languages

Ada, Assembly, Awk, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Pascal, Perl, Prolog, Python, Scala, Swift, VB

Alex tiene un arreglo de $n$ ~n~ strings, él quiere hacer $m$ ~m~ operaciones:

determinar el LCP desde la posición $i$ ~i~ a la posición $j$ ~j~ inclusive,
cambiar todos los strings de $i$ ~i~ a $j$ ~j~ inclusive, por el string $w$ ~w~.

Como Alex es un pequeño programador no sabe como resolver esto en tiempo. Ayúdalo.

Ten en cuenta que el LCP (Longest Common Prefix) de un conjunto de strings, es el mayor prefijo común de estos.

Entrada

La primera línea contiene los enteros $n$ ~n~ y $m \; (1 \leq n, m \leq 10^5)$ ~m \; (1 \leq n, m \leq 10^5)~.

La segunda línea contiene el arreglo de $n$ ~n~ strings. Cada string está separado del anterior por un espacio.

Las siguientes $m$ ~m~ líneas tienen uno los siguientes formatos:

$1 \; i \; j$ ~1 \; i \; j~ (determinar LCP de $i$ ~i~ a $j$ ~j~ inclusive)
$2 \; i \; j \; w$ ~2 \; i \; j \; w~ (cambiar strings de $i$ ~i~ a $j$ ~j~ inclusive por string $w$ ~w~)

Para $i, j$ ~i, j~ tal que $(1 \leq i \leq j \leq n)$ ~(1 \leq i \leq j \leq n)~.

Todas los strings de la entrada están formados por letras minúsculas del alfabeto inglés. El tamaño de cada string no excede los $10$ ~10~ caracteres.

Salida

Para cada operación de tipo $1$ ~1~ imprima el LCP en el rango requerido. Imprima una respuesta por línea.

Ejemplo de entrada

7 3
rhm rh rh rhm r rh r
1 2 3
2 1 6 rhm
1 2 7

Ejemplo de salida

2
1

Comments

0

Sekai02 commented on Oct. 28, 2020, 9:41 p.m. ← edit 2 →

Think a little bit more :)

0

Primervirgen commented on Oct. 28, 2020, 11:07 p.m.

Por gente como tú, el mundo prospera xD

0

Sekai02 commented on Oct. 29, 2020, 12:24 a.m.

lol

-4

Primervirgen commented on Oct. 28, 2020, 8:41 p.m. ← edited →

...