3391 - C5 - Kimetto, Kipsang & Kipchoge 3391 - Kimetto, Kipsang y Kipchoge 3391 - C5 - Kimetto, Kipsang & Kipchoge

Statistics Sub: 238 | AC: 74 | AC%: 31,09 | Score: 2,04
Created by Torneo Argentino de Programación ACM-ICPC 2015 - Fidel I. Schaposnik
Added by fidels (2015-10-12)
Limits
Total Time: 60000 MS | Test Time: 4000 MS |Memory: 256 MB | Output: 64 MB | Size: 16 KB
Enabled languages
Available in

Description

Kenya is the birthplace of some of the best long-distance runners of all times. Indeed, eight of the most recent ten best times in the traditional 41.195 km of the marathon have been set by runners from that country. Dennis Kimetto, Wilson Kipsang and Eliud Kipchoge are three such runners, and they want to beat their discipline's world record once more tomorrow September 27, when they compete in the 42nd edition of the Berlin Marathon.

Kimetto, Kipsang and Kipchoge are good friends, and they like to train together running by the Tana river in order to appreciate the beautiful trees that grow there. There are N trees by the river, which we will number from 1 to N. The i-th tree is of the species S[i] and stands at a distance of i meters from the mouth of the river. Our three runners are especially motivated by the sight of many trees of different species. For this reason, each training day they choose a tree with number K from 1 to N, and then run from the K-th tree following the river, i.e. in the direction of trees K-1, K-2 and so on, stopping only when they see a tree of some species they have already seen that day, or when they reach the mouth of the river, whichever comes first.

For example, if there are N = 4 trees of species S[1] = 1, S[2] = 2, S[3] = 1 and S[4] = 3, when they choose K = 4 the training consists in running 3 meters, from tree number 4 up to tree number 1 (where they stop because this tree is of the same species as tree number 3). However, if they chose K = 2 they would run two meters up to the mouth of the river, where they would stop even without having seen two trees of the same species as they went.

Long-distance running requires decades of training, and in this time it is common for some trees to fall during storms. When this happens, the fallen tree is immediately replaced by another one, not necessarily of the same species. Kimetto, Kipsang and Kipchoge keep a diary where they take note of all the information relevant to their training. In particular, they know the species of all trees, and which number they chose to start running each day of training. Can you help them calculate how much they ran each training day?
Kenya es la cuna de algunos de los mejores corredores de larga distancia de todos los tiempos. Sin ir más lejos, ocho de las últimas diez mejores marcas en los tradicionales 41.195 km de la maratón corresponden a corredores de dicho país. Dennis Kimetto, Wilson Kipsang y Eliud Kipchoge son tres de estos corredores, y se proponen volver a batir el récord mundial de su disciplina mañana 27 de septiembre cuando compitan en la 42da edición de la Maratón de Berlín.

Kimetto, Kipsang y Kipchoge son buenos amigos, y les gusta entrenar juntos corriendo a la vera del río Tana para poder apreciar los hermosos árboles que allí crecen. Hay N árboles junto al río, que vamos a considerar como numerados desde el 1 hasta el N. El i-ésimo árbol es de la especie S[i], y se encuentra a i metros de la desembocadura del río. A nuestros tres corredores los motiva especialmente ver muchos árboles de diferentes especies. Por esta razón, cada día de entrenamiento eligen un número de árbol K entre 1 y N, y luego corren desde el K-ésimo árbol en el sentido del río, es decir hacia los árboles K-1, K-2 y así siguiendo, sin parar hasta volver a ver un árbol de alguna especie que ya hayan visto ese día, o hasta llegar a la desembocadura del río, lo que ocurra primero.

Por ejemplo, si hay N = 4 árboles de las especies S[1] = 1, S[2] = 2, S[3] = 1 y S[4] = 3, cuando eligen K = 4 el entrenamiento consiste en correr 3 metros, desde el árbol número 4 hasta el árbol número 1 (donde se detienen porque éste es de la misma especie que el árbol número 3). En cambio, cuando eligen K = 2 deben correr dos metros hasta la desembocadura del río, donde se detienen a pesar de no haber visto dos árboles de la misma especie en su recorrido.

El entrenamiento de los corredores de larga distancia dura décadas, y en este tiempo es habitual que algunos árboles caigan durante una tormenta. Cuando esto ocurre, el árbol caído es inmediatamente reemplazado por otro, no necesariamente de la misma especie. Kimetto, Kipsang y Kipchoge llevan un diario en el que registran toda la información relevante para su entrenamiento. En particular, saben de qué especie es cada árbol, y qué número de árbol eligieron cada día para comenzar a correr. ¿Pueden ayudarlos a calcular cuánto corrieron durante cada día de entrenamiento?
Kenya is the birthplace of some of the best long-distance runners of all times. Indeed, eight of the most recent ten best times in the traditional 41.195 km of the marathon have been set by runners from that country. Dennis Kimetto, Wilson Kipsang and Eliud Kipchoge are three such runners, and they want to beat their discipline's world record once more tomorrow September 27, when they compete in the 42nd edition of the Berlin Marathon.

Kimetto, Kipsang and Kipchoge are good friends, and they like to train together running by the Tana river in order to appreciate the beautiful trees that grow there. There are N trees by the river, which we will number from 1 to N. The i-th tree is of the species S[i] and stands at a distance of i meters from the mouth of the river. Our three runners are especially motivated by the sight of many trees of different species. For this reason, each training day they choose a tree with number K from 1 to N, and then run from the K-th tree following the river, i.e. in the direction of trees K-1, K-2 and so on, stopping only when they see a tree of some species they have already seen that day, or when they reach the mouth of the river, whichever comes first.

For example, if there are N = 4 trees of species S[1] = 1, S[2] = 2, S[3] = 1 and S[4] = 3, when they choose K = 4 the training consists in running 3 meters, from tree number 4 up to tree number 1 (where they stop because this tree is of the same species as tree number 3). However, if they chose K = 2 they would run two meters up to the mouth of the river, where they would stop even without having seen two trees of the same species as they went.

Long-distance running requires decades of training, and in this time it is common for some trees to fall during storms. When this happens, the fallen tree is immediately replaced by another one, not necessarily of the same species. Kimetto, Kipsang and Kipchoge keep a diary where they take note of all the information relevant to their training. In particular, they know the species of all trees, and which number they chose to start running each day of training. Can you help them calculate how much they ran each training day?

Input specification

The first line contains two integers N and R, representing respectively the number of trees by the river and the number of entries in the training diary (1 <= N, R <= 5 * 10^4). The second line contains N integers S[i] indicating the species of the i-th tree when the training began (1 <= S[i] <= 10^6 for i = 1, 2, ..., N). Each of the following R lines contains the description of an entry in the training diary, in chronological order. This description starts with a character which can be a 'C' if the entry corresponds to a fallen tree or an 'E' if it corresponds to a training day. The entries for fallen trees contain two integers K and S after the 'C', indicating that the K-th tree fell and was replaced by another tree of species S (1 <= K <= N and 1 <= S <= 10^6). The entries for training days contain an integer K after the 'E', indicating that the runners began a training day by running from the K-th tree (1 <= K <= N). There will always be at least one entry for a training day in the input.
La primera línea contiene dos enteros N y R, que representan la cantidad de árboles a la vera del río y la cantidad de registros en el diario de entrenamiento (1 <= N, R <= 5 * 10^4). La segunda línea contiene N enteros S[i] especificando la especie del i-ésimo árbol al comenzar el entrenamiento (1 <= S[i] <= 10^6 para i = 1, 2, ..., N). Cada una de las siguientes R líneas contiene la descripción de un registro del diario, en orden cronológico. La descripción de un registro comienza con un caracter que puede ser una 'C' si corresponde a la caída de un árbol, o una 'E' si corresponde a un día de entrenamiento. Los registros de caída de árboles contienen dos enteros K y S luego de la 'C', indicando que cayó el K-ésimo árbol y fue reemplazado por otro de la especie S (1 <= K <= N y 1 <= S <= 10^6). Los registros de entrenamiento contienen un entero K luego de la 'E', que indica que los corredores comenzaron un día de entrenamiento en el K-ésimo árbol (1 <= K <= N). Siempre habrá al menos un registro de entrenamiento en la entrada.
;jsessionid=3DFD7EB956B1B830B5310C32D4B0BAF0
The first line contains two integers N and R, representing respectively the number of trees by the river and the number of entries in the training diary (1 <= N, R <= 5 * 10^4). The second line contains N integers S[i] indicating the species of the i-th tree when the training began (1 <= S[i] <= 10^6 for i = 1, 2, ..., N). Each of the following R lines contains the description of an entry in the training diary, in chronological order. This description starts with a character which can be a 'C' if the entry corresponds to a fallen tree or an 'E' if it corresponds to a training day. The entries for fallen trees contain two integers K and S after the 'C', indicating that the K-th tree fell and was replaced by another tree of species S (1 <= K <= N and 1 <= S <= 10^6). The entries for training days contain an integer K after the 'E', indicating that the runners began a training day by running from the K-th tree (1 <= K <= N). There will always be at least one entry for a training day in the input.

Output specification

Print one line for each entry corresponding to a training day, indicating the number of meters Kimetto, Kipsang and Kipchoge ran during that day.
Imprimir una línea por cada registro correspondiente a un día de entrenamiento, indicando la cantidad de metros que Kimetto, Kipsang y Kipchoge corrieron durante dicho día.
The first line contains two integers N and R, representing respectively the number of trees by the river and the number of entries in the training diary (1 <= N, R <= 5 * 10^4). The second line contains N integers S[i] indicating the species of the i-th tree when the training began (1 <= S[i] <= 10^6 for i = 1, 2, ..., N). Each of the following R lines contains the description of an entry in the training diary, in chronological order. This description starts with a character which can be a 'C' if the entry corresponds to a fallen tree or an 'E' if it corresponds to a training day. The entries for fallen trees contain two integers K and S after the 'C', indicating that the K-th tree fell and was replaced by another tree of species S (1 <= K <= N and 1 <= S <= 10^6). The entries for training days contain an integer K after the 'E', indicating that the runners began a training day by running from the K-th tree (1 <= K <= N). There will always be at least one entry for a training day in the input.

Sample input

4 2
1 2 1 3
E 4
E 2

Sample output

3
2

Hint(s)

Sample input #2
10 10
1 2 3 4 5 6 7 8 9 10
E 1
E 2
E 3
E 4
E 5
E 6
E 7
E 8
E 9
E 10

Sample output #2
1
2
3
4
5
6
7
8
9
10

Sample input #3
5 7
1 2 3 4 5
E 3
E 5
C 3 1
E 4
C 2 5
E 3
E 5

Sample output #3
3
5
3
2
3
Sample input #2
10 10
1 2 3 4 5 6 7 8 9 10
E 1
E 2
E 3
E 4
E 5
E 6
E 7
E 8
E 9
E 10

Sample output #2
1
2
3
4
5
6
7
8
9
10

Sample input #3
5 7
1 2 3 4 5
E 3
E 5
C 3 1
E 4
C 2 5
E 3
E 5

Sample output #3
3
5
3
2
3
Sample input #2
10 10
1 2 3 4 5 6 7 8 9 10
E 1
E 2
E 3
E 4
E 5
E 6
E 7
E 8
E 9
E 10

Sample output #2
1
2
3
4
5
6
7
8
9
10

Sample input #3
5 7
1 2 3 4 5
E 3
E 5
C 3 1
E 4
C 2 5
E 3
E 5

Sample output #3
3
5
3
2
3

Recommendation

We have carefully selected several similar problems: 3379 | 3675 | 1005 | 3303 | 3232 | 3734