P11236 [KTSC 2024 R1] 水果游戏

**请勿用 C++14 (GCC 9) 提交** 你需要在程序开头加入如下代码： ```cpp #include void prepare_game(std::vector A); int play_game(int l, int r); void update_game(int p, int v); ```

**题目译自 [2024년도 국제정보올림피아드 대표학생 선발고사 - 1차 선발고사](https://www.ioikorea.kr/archives/ioitst/2024/) T2 「[과일 게임](https://assets.ioikorea.kr/ioitst/2024/1/fruitgame/fruitgame_statement.pdf)」** 水果游戏是一款将各种水果合并成更大水果的游戏。游戏板可以表示为一个序列 $X[0], X[1], \cdots, X[K-1]$，其中每个数字代表一种水果的编号，编号越大，水果越大。 玩家可以执行合并操作，将相邻且相同的两个水果合并成更大的水果。合并操作定义如下： 合并：在表示为 $X[0], X[1], \cdots, X[K-1]$ 的游戏板上，选择一个整数 $0 \leq i \leq K-2$，如果 $X[i]=X[i+1]$，则将游戏板变为 $X[0], \cdots, X[i-1], X[i]+1, X[i+2], \cdots, X[K-1]$。 玩家的目标是，在给定初始游戏板的情况下，通过 $0$ 次或多次合并操作，尽可能生成更大的水果。 例如，游戏板 $X=[2,1,1,3,2]$，因为 $X[1]=X[2]$，选择 $i=1$ 进行合并操作，游戏板变为 $X=[2,2,3,2]$。然后，因为 $X[0]=X[1]$，选择 $i=0$ 进行合并操作，游戏板变为 $X=[3,3,2]$。最后，因为 $X[0]=X[1]$，选择 $i=0$ 进行合并操作，游戏板变为 $X=[4,2]$。这样可以得到编号为 $4$ 的水果，这是可以得到的最大水果编号。 给定一个长度为 $N$ 的序列 $A$，序列中的元素可以在中途发生变化，并且这些变化是累积的。每当给定一个满足 $0 \leq l \leq r \leq N-1$ 的整数对 $(l, r)$ 时，你需要计算由 $A[l], \cdots, A[r]$ 表示的游戏板上可以得到的最大水果编号。序列的元素变化或给定的整数对的次数总共为 $Q$ 次。 你需要实现以下函数： ```cpp void prepare_game(std::vector A); ``` - `A`：大小为 $N$ 的整数数组。 - 该函数只会被调用一次，并且在其他所有函数调用之前调用。 - 如果需要进行预处理或设置全局变量，可以在此函数中实现。 ```cpp int play_game(int l, int r); ``` - 该函数应返回由 $A[l], \cdots, A[r]$ 组成的游戏板上可以得到的最大水果编号。 - 该函数会被调用多次。 ```cpp void update_game(int p, int v); ``` - 该函数应将 $A[p]$ 的值更改为 $v$。 - `play_game` 函数或 `update_game` 函数的调用次数总共为 $Q$ 次。 注意，提交的代码中不应包含任何输入输出操作。

示例评测程序按以下格式读取输入： - 第 $1$ 行：$N$ - 第 $2$ 行：$A[0]\,A[1]\,\cdots\,A[N-1]$ - 第 $3$ 行：$Q$ - 第 $3+i$ $(1 \leq i \leq Q)$ 行：如果调用 `play_game` 函数，则为 `1 l r`；如果调用 `update_game` 函数，则为 `2 p v`

示例评测程序输出： - 第 $i$ 行：第 $i$ 次调用 `play_game` 函数返回的值

对于所有输入数据，满足： - $1 \leq N, Q \leq 10^5$ - 对于所有 $i$ $(0 \leq i \leq N-1)$，$1 \leq A[i] \leq 10$ - 对于所有 `play_game` 调用，$0 \leq l \leq r \leq N-1$ - 对于所有 `update_game` 调用，$0 \leq p \leq N-1, 1 \leq v \leq 10$ 详细子任务附加限制及分值如下表所示。 | 子任务 | 分值 | 附加限制 | | :-: | :-: | :-: | | $1$ | $5$ | $N \leq 10,Q \leq 10$ | | $2$ | $6$ | $N \leq 600,Q \leq 600$ | | $3$ | $8$ | $N \leq 4000,Q \leq 4000$；对于所有 $i$ $(0 \leq i \leq N-1)$，$A[i] \leq 2$；对于所有 `update_game` 调用，$v \leq 2$ | | $4$ | $15$ | $N \leq 4000,Q \leq 4000$ | | $5$ | $12$ | 对于所有 $i$ $(0 \leq i \leq N-1)$，$A[i] \leq 2$；对于所有 `update_game` 调用，$v \leq 2$ | | $6$ | $14$ | 不会调用 `update_game` | | $7$ | $40$ | 无附加限制 |