Multiplicación en Rango


Submit solution

Points: 100 (partial)
Time limit: 2.0s
Memory limit: 512M

Author:
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\}, donde inicialmente A_i = 1 para 1 \le i \le N, a usted se le darán varias consultas de dos tipos:

  • Tipo 1: 1\ x\ y. Para este tipo de consulta, usted debe imprimir A_x + A_{x + 1} + \dots + A_y.

  • Tipo 2: 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 y y, multiplicándolo por k, (A_i := A_i \cdot k, para x \leq i \leq y).

Dadas 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 (1 \leq N \leq 1 000 000) y M (1 \leq M \leq 10 000), la cantidad de elementos de la secuencia y el número de consultas respectivamente. 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, donde 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, donde x, y son enteros, (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).

Ejemplo de Entrada

10 3
1 1 4
0 2 3 2
1 1 4

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) con SQRT Decomposition, la idea de este algoritmo es dividir un arreglo de tamaño N en bloques de tamaños \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í.