Respondiendo Preguntas


Submit solution

Points: 100 (partial)
Time limit: 4.0s
Memory limit: 64M

Author:
Problem type
Allowed languages
Ada, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Pascal, Prolog, Python, Swift, VB

Hay N celdas contiguas numeradas de 1 a N, que identifican la secuencia A.

Inicialmente, cada celda contiene los valores A[1] = A[2] = ..., A[N] = 0 (A[i] = 0, para todo 1 \leq i \leq N): Esto significa que cada celda inicialmente es igual a 0.

Un subgrupo continuo de celdas (siempre uno, dos o tres celdas) pueden ser actualizadas de la siguiente forma – Update (i, k):

  • A la celda numerada i + 1 se le adiciona k, si la celda existe.
  • A la celda numerada i - 1 se le adiciona k, si la celda existe.
  • A la celda i se le adiciona 2*k.

Por ejemplo, si N = 6 las operaciones update [3, 6] y [4, 7] actúan de la siguiente forma:

Inicialmente: {0, 0, 0, 0, 0, 0}

Update[3, 6]: {0, 6, 12, 6, 0, 0}

Update[4, 7]: {0, 6, 19, 20, 7, 0}

Después de ejecutar algunas operaciones de actualización, podríamos estar interesados en responder preguntas de la siguiente forma:

  1. Un rango [u, v] es definido tal que u ≤ v.
  2. La respuesta a la suma de los valores de la celdas en el rango [u, v] (ambos u y v incluidos) módulo 10^4.

Dado N y U consultas de actualización, usted deberá escribir un programa capaz de responder Q preguntas.

Entrada

La primera línea contiene tres enteros: N, U y Q (1 \leq N, U, Q \leq 10^6), representando el número de celdas, el número de operaciones de actualización, y el número de consultas respectivamente. Cada una de las siguientes U + Q líneas contienen una de dos posibles operaciones (actualización o consulta):

  • Actualización: Indicado por el número 1, seguido por dos enteros i y k (1 \leq i \leq N) y (1 \leq k \leq 10^6) separados por un espacio, indicando la operación de actualización.
  • Consulta: Indicado por el número 2, seguido por dos enteros u y v (1 \leq u \leq v \leq N) separados por un espacio indicando la operación de consulta.

Salida

Para cada pregunta [u, v] usted deberá imprimir la suma de todas las celdas contiguas empezando en u y terminando en v módulo 10^4.

Ejemplo de Entrada

6 2 2
1 3 6
2 4 6
1 4 7
2 1 6

Ejemplo de Salida

6
52

Comments


  • -2
    Hd  commented on Dec. 22, 2023, 4:53 a.m.

    C++ Te amo por tu buena optimización


  • -1
    LeandroGamer  commented on Sept. 18, 2023, 9:06 p.m. edit 2

    XD