Le jeu de fruits consiste à combiner des fruits de différents types pour créer des types de fruits plus gros. Le plateau peut être représenté par une suite $X[0],X[1],\ldots,X[K-1]$. Chaque nombre est l’identifiant d’un type de fruit, et un identifiant plus grand signifie un fruit plus gros.

Le joueur peut effectuer une opération de fusion, combinant deux fruits adjacents du même type en un fruit plus gros. Cette opération est définie comme suit.

Fusion : sur le plateau $X[0],X[1],\ldots,X[K-1]$, choisissez un entier $0\le i\le K-2$. Si $X[i]=X[i+1]$, remplacez le plateau par $X[0],\ldots,X[i-1],X[i]+1,X[i+2],\ldots,X[K-1]$.

Étant donné le plateau initial, le but du joueur est de créer un gros fruit en utilisant zéro ou plusieurs opérations de fusion.

Par exemple, sur le plateau $X=[2,1,1,3,2]$, puisque $X[1]=X[2]$, choisir $i=1$ et fusionner transforme le plateau en $X=[2,2,3,2]$. Puisque $X[0]=X[1]$, choisir $i=0$ et fusionner le transforme ensuite en $X=[3,3,2]$. Enfin, puisque $X[0]=X[1]$, choisir $i=0$ et fusionner donne $X=[4,2]$. On crée ainsi un fruit d’identifiant $4$, le plus grand identifiant que l’on puisse obtenir.

On vous donne une suite $A$ de longueur $N$. Ses éléments peuvent changer, et les changements sont cumulatifs. Chaque fois qu’une paire d’entiers $(l,r)$ vérifiant $0\le l\le r\le N-1$ est donnée, trouvez le plus grand identifiant de fruit que l’on peut obtenir sur le plateau $A[l],\ldots,A[r]$. Il y a $Q$ événements au total, chacun étant une modification d’élément ou la présentation d’une paire.

Détails d'implémentation

Vous devez implémenter les fonctions suivantes.

void prepare_game(std::vector<int> A)

• $A$ : un tableau d’entiers de taille $N$.
• Cette fonction est appelée exactement une fois, avant toutes les autres fonctions.
• Vous pouvez effectuer dans cette fonction les prétraitements ou l’initialisation des variables globales nécessaires aux appels ultérieurs.

int play_game(int l, int r)

• Cette fonction doit renvoyer le plus grand identifiant de fruit que l’on peut obtenir sur le plateau $A[l],\ldots,A[r]$.
• Cette fonction est appelée au moins une fois.

void update_game(int p, int v)

• Remplacez la valeur de $A[p]$ par $v$.

Le nombre total d’appels à play_game et à update_game est $Q$.

Vous ne devez exécuter de fonctions d’entrée/sortie nulle part dans le code source soumis.

Remarque

$A[i],\ldots,A[j]$ est la suite de longueur $j-i+1$ constituée des éléments de $i$ à $j$ de $A$. Par exemple, lorsque $A=[3,5,7,2,9]$, $A[1],\ldots,A[3]$ vaut $[5,7,2]$, et $A[4],\ldots,A[4]$ vaut $[9]$.

Contraintes

• $1\le N,Q\le100\,000$
• $1\le A[i]\le10$ ($0\le i\le N-1$).
• Pour chaque appel à play_game : $0\le l\le r\le N-1$.
• Pour chaque appel à update_game : $0\le p\le N-1$, $1\le v\le10$.

Sous-tâches

1 (5 points)

• $N\le10$.
• $Q\le10$.

2 (6 points)

• $N\le600$.
• $Q\le600$.

3 (8 points)

• $N\le4\,000$.
• $Q\le4\,000$.
• $A[i]\le2$ ($0\le i\le N-1$).
• Pour chaque appel à update_game : $v\le2$.

4 (15 points)

• $N\le4\,000$.
• $Q\le4\,000$.

5 (12 points)

• $A[i]\le2$ ($0\le i\le N-1$).
• Pour chaque appel à update_game : $v\le2$.

6 (14 points)

• update_game n’est pas appelée.

7 (40 points)

• Aucune contrainte supplémentaire.

Exemples

Exemples 1

Considérons le cas $N=5$, $A=[2,1,1,3,4]$.

L’évaluateur appelle les fonctions suivantes dans l’ordre.

prepare_game([2, 1, 1, 3, 4])
play_game(0, 4) = 5
update_game(2, 3)
play_game(2, 4) = 5
update_game(1, 2)
play_game(0, 2) = 4

Exemples 2

Considérons le cas $N=7$, $A=[1,1,1,1,2,2,2]$.

L’évaluateur appelle les fonctions suivantes dans l’ordre.

prepare_game([1, 1, 1, 1, 2, 2, 2])
play_game(0, 6) = 4
play_game(2, 4) = 3
update_game(6, 4)
play_game(4, 6) = 4
play_game(0, 6) = 5

Évaluateur d’exemple

L’évaluateur d’exemple lit l’entrée dans le format suivant.

• Ligne 1: $N$.
• Ligne 2: $A[0]\ A[1]\ \cdots\ A[N-1]$.
• Ligne 3: $Q$.
• Ligne $3+i$ ($1\le i\le Q$) : 1 l r pour un appel à play_game, ou 2 p v pour un appel à update_game.

L’évaluateur d’exemple affiche ce qui suit.

• Ligne $i$ : la valeur renvoyée par le $i$-ième appel à play_game.

Notez que l’évaluateur d’exemple peut différer de l’évaluateur utilisé lors de la correction réelle.