别急。先更一波T2,T3。
七管荧光灯
可以状压打表可以发现：一种局面为必败状态当且仅当满足 \(a_{1}=x,a_{2}=x,a_{3}=x,a_{4}=y,a_{5}={z},a_{6}=z,a_{7}=z\) 且 \(x \oplus y \oplus z=0\)。
然后就可以数位 dp 了，记个 \(f_{i,0/1,0/1,0/1,0/1,0/1,0/1}\)。随便跑跑就行。
字符串
题意：
有一个字符串 \(S\)，需要支持 \(Q\) 个操作。
- 操作 1：给出条件 \(l,r\) 表示 \(S[l...r]\) 为一个回文串。
- 操作 2：如果 \(s[a...b]\) 和 \(s[x...y]\) 一定相等就输出 Equal，一定不相等则输出 Not equal，无法判断则输出 Unknown。
\(n \le 10^5, Q \le 2 \times 10^5\)。
分析：
显然，Not equal 的充要条件为 \(a-b\ne x-y\)。
不难得到一个暴力做法：
- 操作 1：把 \([l...mid]\) 到 \([mid+1,r]\) 暴力连边。
- 操作 2：判断 \(s[a]\) 与 \(s[x]\)，\(s[a+1]\) 与 \(s[x+1]\) ... \(s[b]\) 与 \(s[y]\) 是否均在同一个联通块类。
利用并查集时间复杂度可以做到 \(O(nQ \log n)\)。
考虑操作 2，如果我们知道能动态维护每个点的 fa，那么就能利用哈希快速判断是否合法。
可以发现，一个 \(n\) 个点的并查集的有效合并次数为 \(n-1\)。
只需要保证在操作 1 时都是进行的有效的合并操作，那么时间复杂度就能降下来。
具体地，开两棵线段树分别维护每个区间正着和反着的哈希值。
在操作 1 时，可以利用二分查找第一个有效的合并操作，使用启发式暴力合并即可。
时间复杂度 \(O(n \log ^2 n)\)。