Respondiendo Preguntas
Hay celdas contiguas numeradas de
a
, que identifican la secuencia
.
Inicialmente, cada celda contiene los valores , para todo
: Esto significa que cada celda inicialmente es igual a
.
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
se le adiciona
, si la celda existe.
- A la celda numerada
se le adiciona
, si la celda existe.
- A la celda
se le adiciona
.
Por ejemplo, si 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
.
Dado y
consultas de actualización, usted deberá escribir un programa capaz de responder
preguntas.
Entrada
La primera línea contiene tres enteros: ,
y
, 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
líneas contienen una de dos posibles operaciones (actualización o consulta):
- Actualización: Indicado por el número
, seguido por dos enteros
y
y
separados por un espacio, indicando la operación de actualización.
- Consulta: Indicado por el número
, seguido por dos enteros
y
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 y terminando en
módulo
.
Ejemplo de Entrada
6 2 2
1 3 6
2 4 6
1 4 7
2 1 6
Ejemplo de Salida
6
52
Comments
C++ Te amo por tu buena optimización
Yo ese
XD