首先考察 $n, m \le 5000$ 怎么解决，这明显需要我们给出一个 $O(n)$ 单次求取答案的算法。

不难发现，假设对于原始串 $str$ 做若干次操作，每次操作形如一些连续段的扩展与收缩，可以维护每个连续段长度以及类型，还有下一步是收缩还是扩展，当然也有可能不变，每次当一个连续段被完全删去时我们就重构一下这个连续段旁边的段的结构，将其合并，继续这个过程，复杂度是单次 $O(n)$ 的。

接下来的部分分中对正解指导意义最强的就是 $l = 1$ 的部分分，它直接明示了你不能套用上述结构，要转而思考一些支持前缀依赖转移的结构优化你单次求取答案的过程。我们可以构造以下算法，扫取前缀的同时维护一个栈：

• 当前扫到了 $str_i$，假设栈顶元素能够战胜 $str_i$，那么不进行任何操作，因为在向左扩展的时候这个段会被干掉。
• 当前扫到了 $str_i$，假设栈顶元素和 $str_i$ 属于同类型，还是不变，因为如果栈顶在我们的过程中会被干掉，那么 $str_i$ 同样会被干掉。
• 当前扫到了 $str_i$，假设 $str_i$ 能够战胜栈顶元素，那么将栈顶弹出，可以证明，弹出之后的栈顶与 $str_i$ 是一样的，不需要弹入 $str_i$。

最后的栈结构从栈底到栈顶会形如 $\texttt{GMPGMP.../MPGMPG.../PGMPGM...}$ 三种中的一种，此时考虑左边界收缩，那么栈底可以将后面所有元素全部干掉，下面将给出证明：

考察每一个连续段 $i$，假设在它前面的连续段为 $i - 1$，在它后面的连续段为 $i + 1$，那么本质上，$i$ 只分为这么两类：

• $i$ 所对应的 $i - 1$，$i + 1$ 中有一个在胁迫它。
• $i$ 所对应的 $i - 1$，$i + 1$ 中没有段在胁迫它。

那么，容易发现，在第一种情况下，$i$ 必然要完，仍然可以将其分为两类考虑：

• $i - 1$，$i + 1$ 同时在胁迫 $i$。
• $i - 1$，$i + 1$ 只有一个在胁迫 $i$。

对于第一种情况，$i$ 要完的理由是，在 $i$ 完了之前，$i - 1$ 和 $i + 1$ 必然都不会完（考察边界处的情况），那么能够支持完全干掉 $i$。

对于第二种情况，将假设 $i - 1$ 在胁迫它，那么在 $i$ 完之前，$i - 1, i$ 的边界处必然会有一个位置追着 $i$ 往右边走，那么结果无非只有两个：在干掉右边一些串后，遇到强敌，归纳到第一种情况，或者干掉了右边全部的串，撞墙了所以会被 $i - 1$ 蚕食到没有。容易归纳递推出对于所有满足条件的 $i$ 上述两点成立，$i + 1$ 的情况与 $i - 1$ 同理。

对于左右两边不存在段胁迫 $i$ 的情况，这并不说明 $i$ 不会完，需要递归到 $i - 1, i + 1$，$i$ 随时有可能被干掉，只有到最后剩下那一个才是答案。

上述用栈模拟的过程本质上是在实现这个归纳的过程，证明过程也说明了答案与连续段长度无关。

但是区间查询是非常麻烦的，它可能需要你的结构满足一定可合并性，貌似整个栈结构的合并不太好（可能并不具有可合并性），即使实现出来，它的常数也无法通过最后一档苛刻的测试点，这里用一个巧妙的过程刻画答案：

• 记录每个时刻栈所对应的大小（对于 $str$ 的每个前缀 $i$ 考虑）为 $f_i$，显然 $f_i = f_{i - 1} / f_{i - 1} + 1 / \max(1, f_{i - 1} - 1)$，可以线性递推。

那么对于 $str$ 全局而言，答案就是 $f_i = 1$ 的最后一个位置对应的元素，原因是简单的。

难道我要对于区间 $[l, r]$ 都要维护一个这样的东西吗？并不需要，发现对于 $[1, l - 1]$ 的栈结构下，依次加入 $[l, r]$ 内的元素得到的 $f$，与 $[l, r]$ 单独加入得到的 $f$，其相对大小完全一样（对于相等的刻画略有偏差，不过不影响求解的过程），那么区间 $[l, r]$ 的答案就变成了全局 $f_i$ 在区间内最后一个最小的位置所对应的元素，查询和修改都是简单的可以用线段树实现，总时间复杂度 $O(tn\log n)$。

最终代码常数极小，可以以很快的速度通过最后一档测试点。