Fruit Game

This problem is adapted from the 2024 International Olympiad in Informatics Korea Selection Contest, T2 "Fruit Game". In this game, you are given a board represented as a sequence \(X[0], X[1], \ldots, X[K-1]\), where each number corresponds to a type of fruit (with larger numbers representing larger fruits). You can perform a merge operation on any two adjacent identical fruits. The merge operation is defined as:

Merge: Given board \(X[0],X[1],\ldots,X[K-1]\), choose an integer \(0 \le i \le K-2\) such that \(X[i] = X[i+1]\). Replace these two fruits by a single fruit with number \(X[i] + 1\). In other words, the board becomes \(X[0], \ldots, X[i-1], X[i]+1, X[i+2], \ldots, X[K-1]\).

The goal is, starting with an initial game board, to perform zero or more merge operations so as to obtain as high a fruit number as possible. For instance, consider the board \([2,1,1,3,2]\). One optimal sequence of operations is:

• Merge the fruits at positions 1 and 2 (both 1's) to obtain \([2,2,3,2]\).
• Merge the fruits at positions 0 and 1 (both 2's) to obtain \([3,3,2]\).
• Merge the fruits at positions 0 and 1 (both 3's) to obtain \([4,2]\).

The maximum fruit obtained is 4. In addition, the board is represented by an array \(A\) whose values can change over time. You will be given a series of operations, each being either:

• A query: given indices \(l\) and \(r\) (with \(0 \le l \le r \le N-1\)), compute the maximum fruit number that can possibly be obtained from the subarray \(A[l],A[l+1],\ldots,A[r]\) after performing any number of merge operations.
• An update: change the value at position \(p\) to a new value \(v\).

You need to implement the following functions (without any input/output operations):

void prepare_game(vector A);
// Called once. Initialize any global data with the initial array A of size N.

int play_game(int l, int r);
// Return the maximum fruit number that can be obtained from the subarray A[l..r].

void update_game(int p, int v);
// Update A[p] to v.

Note: In the resulting board from a sequence of operations, the maximum fruit number is the maximum over all fruits present (including intermediate fruits produced during merges). A subarray might have mergeable parts that yield a fruit value higher than any fruit originally present.

Hint: One way to decide if a contiguous segment \(A[i..j]\) can be merged into a single fruit is to use dynamic programming. Define \(dp[i][j]\) as the fruit number if the segment \(A[i..j]\) can be completely merged into one fruit, otherwise set it to -1. For a single fruit, \(dp[i][i] = A[i]\), and for a segment \(A[i..j]\) with \(i < j\), if there exists a partition \(i \le k < j\) such that \(dp[i][k] \neq -1\), \(dp[k+1][j] \neq -1\) and \(dp[i][k] = dp[k+1][j]\), then \(dp[i][j] = dp[i][k] + 1\).

inputFormat

This is a library problem. You are provided with three functions that will be called by the judge:

• prepare_game(vector<int> A): Initializes the game board with the given array A of size N.
• play_game(int l, int r): Returns the maximum fruit number obtainable from the subarray A[l..r] after applying merge operations optimally.
• update_game(int p, int v): Updates the fruit at index p to the value v.

The total number of calls to play_game and update_game is Q. There is no standard input.

outputFormat

This is a library problem. The play_game function should return an integer representing the maximum fruit number obtainable from the specified subarray after any sequence of merges, while prepare_game and update_game do not produce any output.

sample

Initial array: [2, 1, 1, 3, 2]
Operations:
play_game(0, 4) -> Expected output: 4
update_game(2, 2)
play_game(0, 4) -> Expected output: 3

4
3

</p>