$\large\text{Outline}$
- 反套路思维题。
$\large\text{Algorithm}$
-
考虑常规做法，然而区间 $\texttt{DP}$ 面对这道题线性的复杂度要求其实是没什么前途的，最多优化到 $O(T\cdot n^3)$。
-
我们可以发现 $\texttt{DP}$ 的本质与暴力搜索并无二致，注重的是最终获胜状态的可能性以及它们由什么状态得来，在这道题的背景下，这个思维陷入了误区。
-
可以发现如果枚举位置 $i$ 将问题转换为判断 $i$ 是否可以获胜这一判定性问题会更加可做，这样我们的关注点就从复杂的状态转移改换到这道题操作本身具有的性质上。
-
为了分析更加方便，我们用 ${0,1,2}$ 代替 ${\texttt{R},\texttt{S},\texttt{P}}$ 三个元素，指定它们是一一对应的，我们用它去更方便地表述一种胜败关系：取值 $x$ 胜于 $(x+1)\mod3$，负于 $(x+2)\mod 3$。
-
我们设基准于 $x_0 = x，x_1 = (x+1)\mod 3,x_2 = (x+2)\mod 3$。
-
对于位置 $i$ 的取值 $x$，它的获胜状态是显然的：序列的 $[1,i-1],[i+1, n]$ 区间可以通过内部的操作消成取值全为 $x_1$ 的序列。
-
因此我们只用考虑怎么判断某段前缀或后缀区间能否被消成全为 $x_1$ 的序列。
-
设区间为 $[l,r]$，考虑一个值恰等于 $x_1$ 的位置 $p$（如果没有那么这个区间也不可能被消去），那么我们希望 $p$ 能成为最终留下的若干元素之一，因此我们再次将区间分成 $[l,p-1],[p+1,r]$。这两个区间的讨论没有细节上的差别。
-
考虑其中一个区间，我们发现如果其中存在值等于 $x_2$ 的元素，它一定可以被消去。
-
如上序列中，我们只需保持某个 $x_1$ 不动，剩下的元素可以互相相消，最后剩下的序列一定只有 $x_1,x_2$，此时用 $x_1$ 消掉所有 $x_2$ 即可。
-
这一步是在口胡，但手玩一下不难验证。
-
而如果一个区间里没有 $x_2$，那么其必然为全 $x_1$ 才满足条件，这一结论是显然的。
-
至此我们分析完了 $p$ 的左右区间可被消除的条件，无非两个：
- 存在 $x_2$。
- 不存在 $x_0$。
-
因此我们在判断 $i$ 是否可以获胜时在 $[1,i-1], [i+1, n]$ 两区间额外枚举 $p$ 满足 $a_p=x_1$ 后判断 $[l,p-1],[p+1,r]$ 内的元素种类，可以做到 $O(n^2)$ 的时间复杂度。
-
注意到我们需要讨论的 $[1,i-1],[i+1,n]$ 分别为前缀和后缀，可以考虑优化，而枚举在前后缀区间内枚举 $p$ 再分成的两个区间合法情况有四种：
- 左右区间均存在 $x_2$。
- 左区间存在 $x_2$，右区间不存在 $x_0$。
- 左区间不存在 $x_0$，右区间存在 $x_2$。
- 左右区间均不存在 $x_0$。
-
首先处理情况 1 是非常简单的，左右区间均存在 $x_2$ 时，算上中间的分割点 $p$ 会构成子序列 $x_2,x_1,x_2$，我们只用算出它在前后缀中最早完整出现的位置并判断该位置是否属于当前计算的前后缀区间即可。
-
处理 2、3、4 可以用一个非常神奇的判断，我们只需找到前后缀区间中第 $1$ 个 $x_1$ 和最后一个 $x_1$，判断它们作为 $p$ 点时左右分割出的两区间能否被消去即可。
-
这显然是对的，只不过思路很神奇……
$\large\text{Notes}$
- 有些问题 $\texttt{DP}$ 处理的局限性是明显的。