Multiplicación en Rango
Dada una secuencia , donde inicialmente para , a usted se le darán varias consultas de dos tipos:
Tipo 1: . Para este tipo de consulta, usted debe imprimir .
Tipo 2: . Para este tipo de consulta, usted debe modificar el valor de cada número en la secuencia entre las posiciones y , multiplicándolo por , (, para ).
Dadas consultas, su programa debe procesarlas en el orden en que son dadas e imprimir los resultados a todas las consultas de tipo 1.
Entrada
La entrada tiene varios casos de prueba:
La primera línea de cada caso de prueba contiene dos números enteros y , la cantidad de elementos de la secuencia y el número de consultas respectivamente. líneas siguen con consultas de uno de los dos tipos explicados.
- En caso de que sea una consulta de tipo 1, la línea será de la forma , donde son enteros, .
- En caso de que sea una consulta de tipo 2, la línea será de la forma , donde son enteros, .
Salida
Para las consultas del tipo 1, imprima su resultado módulo .
Ejemplo de Entrada
10 3
1 1 4
0 2 3 2
1 1 4
Ejemplo de Salida
4
6
Comments
Alguien puede revisar mi code por favor y decirme que tengo mal ._.
Hola alguien puede revisar mi código y decirme q tengo mal. A desir verdad no sé muy bien lazy propagation pero he probado muchos casos prueba y todos me dan bien. Por favor alguien me puede ayudar
Hola, alguien que pueda revisar mi code y decirme xq me da WA, me da el caso de prueba y no entiendo que pueda estar mal •_•
Hola, alguien pudiera revisar mi sol y decirme en que puedo mejorar, me da WA y para mi esta bien. Nota: Acabe de aprender lazy propagation.. Ayudenme ahí.
Según vi en tu código, para cada nodo llevas un valor llamado
lazy
, que mantiene la información pendiente por actualizar. Dicho valor debería ser inicialmente1
, y además, cuando lo propagas, deberías multiplicarlo, no sumarlo.gracias bro
erne1309 , para multiplicar los valores de un rango de a - b por un valor k ,solo tienes que multiplicar la suma de ese intervalo por k , prueba con ejemplos para que lo veas.
Alguien por favor me explique como puedo multiplicar en el update en rango
También puede resolverse en con SQRT Decomposition, la idea de este algoritmo es dividir un arreglo de tamaño en bloques de tamaños y mantener información sobre los valores del arreglo dentro de cada bloque. Puedes aprender más aquí.
Se resuelve fácilmente usando Segment Tree con Lazy Propagation. Es bien estándar, puedes aprender aquí.