Multiplicación en Rango

Points: 100 (partial)

Time limit: 2.0s

Memory limit: 512M

Author:

antonio_bouza

Problem type

Allowed languages

Ada, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Pascal, Prolog, Python, Swift, VB

Dada una secuencia $A = \{A_1, A_2, \dots, A_n\}$ ~A = \{A_1, A_2, \dots, A_n\}~, donde inicialmente $A_i = 1$ ~A_i = 1~ para $1 \le i \le N$ ~1 \le i \le N~, a usted se le darán varias consultas de dos tipos:

Tipo 1: $1\ x\ y$ ~1\ x\ y~. Para este tipo de consulta, usted debe imprimir $A_x + A_{x + 1} + \dots + A_y$ ~A_x + A_{x + 1} + \dots + A_y~.
Tipo 2: $0\ x\ y\ k$ ~0\ x\ y\ k~. Para este tipo de consulta, usted debe modificar el valor de cada número en la secuencia entre las posiciones $x$ ~x~ y $y$ ~y~, multiplicándolo por $k$ ~k~, ( $A_i := A_i \cdot k$ ~A_i := A_i \cdot k~, para $x \leq i \leq y$ ~x \leq i \leq y~).

Dadas $M$ ~M~ 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 $N$ ~N~ $(1 \leq N \leq 1 000 000)$ ~(1 \leq N \leq 1 000 000)~ y $M$ ~M~ $(1 \leq M \leq 10 000)$ ~(1 \leq M \leq 10 000)~, la cantidad de elementos de la secuencia y el número de consultas respectivamente. $M$ ~M~ 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 $0\ x\ y\ k$ ~0\ x\ y\ k~, donde $x, y, k$ ~x, y, k~ son enteros, $(1 \leq x \leq y \leq N, 1 \leq k \leq 10^9)$ .
En caso de que sea una consulta de tipo 2, la línea será de la forma $1\ x\ y$ ~1\ x\ y~, donde $x, y$ ~x, y~ son enteros, $(1\leq x \leq y\leq N)$ ~(1\leq x \leq y\leq N)~.

Salida

Para las consultas del tipo 1, imprima su resultado módulo $1 000 000 009, (10^9 + 9)$ ~1 000 000 009, (10^9 + 9)~.

Ejemplo de Entrada

Ejemplo de Salida

4
6

Comments

0

Bynner commented on April 2, 2023, 4:27 a.m.

Alguien puede revisar mi code por favor y decirme que tengo mal ._.

-1

Samuel08DA commented on Feb. 27, 2023, 1:04 a.m.

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

0

Ali commented on Oct. 9, 2022, 11:42 p.m.

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 •_•

-1

xcaim commented on April 1, 2022, 2:18 p.m.

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í.

0

aniervs commented on April 1, 2022, 4:25 p.m.

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 inicialmente 1, y además, cuando lo propagas, deberías multiplicarlo, no sumarlo.

1

erne1309 commented on July 15, 2021, 7:30 p.m.

gracias bro

1

Osnielfc_07 commented on July 15, 2021, 7:13 p.m.

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.

1

erne1309 commented on July 15, 2021, 5:02 p.m. ← edit 4 →

Alguien por favor me explique como puedo multiplicar en el update en rango

0

eblabrada commented on July 18, 2021, 5:09 p.m.

También puede resolverse en $O(M \sqrt N)$ ~O(M \sqrt N)~ con SQRT Decomposition, la idea de este algoritmo es dividir un arreglo de tamaño $N$ ~N~ en bloques de tamaños $\sqrt N$ ~\sqrt N~ y mantener información sobre los valores del arreglo dentro de cada bloque. Puedes aprender más aquí.

0

aniervs commented on July 17, 2021, 6:04 p.m.

Se resuelve fácilmente usando Segment Tree con Lazy Propagation. Es bien estándar, puedes aprender aquí.