Respondiendo Preguntas

Points: 100 (partial)

Time limit: 4.0s

Memory limit: 64M

Author:

antonio_bouza

Problem type

Allowed languages

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

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

Inicialmente, cada celda contiene los valores $A[1] = A[2] = ..., A[N] = 0 (A[i] = 0$ $A [1] = A [2] = . . ., A [N] = 0 (A [i] = 0$ , para todo $1 \leq i \leq N)$ $1 \leq i \leq N)$ : Esto significa que cada celda inicialmente es igual a $0$ $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$ $i + 1$ se le adiciona $k$ $k$ , si la celda existe.
A la celda numerada $i - 1$ $i - 1$ se le adiciona $k$ $k$ , si la celda existe.
A la celda $i$ $i$ se le adiciona $2*k$ $2 * k$ .

Por ejemplo, si $N = 6$ $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:

Un rango [u, v] es definido tal que u ≤ v.
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$ $10^{4}$ .

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

Entrada

La primera línea contiene tres enteros: $N$ $N$ , $U$ $U$ y $Q (1 \leq N, U, Q \leq 10^6)$ $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$ $U + Q$ líneas contienen una de dos posibles operaciones (actualización o consulta):

Actualización: Indicado por el número $1$ $1$ , seguido por dos enteros $i$ $i$ y $k$ $k$ $(1 \leq i \leq N)$ $(1 \leq i \leq N)$ y $(1 \leq k \leq 10^6)$ $(1 \leq k \leq 10^{6})$ separados por un espacio, indicando la operación de actualización.
Consulta: Indicado por el número $2$ $2$ , seguido por dos enteros $u$ $u$ y $v$ $v$ $(1 \leq u \leq v \leq N)$ $(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$ $u$ y terminando en $v$ $v$ módulo $10^4$ $10^{4}$ .

Ejemplo de Entrada

Copy

Ejemplo de Salida

Copy

6
52

Comments

2

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

C++ Te amo por tu buena optimización

0

JoJo_Cubano_13 commented on Jan. 18, 2024, 8:39 p.m.

Yo ese

0

LeandroGamer commented on Sept. 18, 2023, 9:06 p.m. ← edit 2 →

XD