1117总结
1117总结
T1
问的是对于每个跳棋能走到多少个格子，不重不漏那种。
发现对于一个棋子，由于它跳的时候其它的不能动，所以本质上如果弄成图处理不会出问题，问题变成了无向图中一个点可以到多少个点，就是联通块问题，不妨先把所有可能可达的点弄出来建一个图，点数 \(O(n)\)，然后问一个棋子，要对图做一下改变，具体的是加一些边连向一个新点，问新点所在连通块大小。
可以可撤销并查集，当然也可以直接枚举做，相邻的情况是平凡的，特判掉。
场上写挂是因为数组开小了，点的数量是 \(7n\) 而不是 \(6n\)。
T2
首先判掉没有 \(GT\) 的情况，直接选最后一个。
然后如果有 \(GT\) ，那么一左端点一定是第一个 \(G\) 或者 \(T\)，然后左端点固定，需要比较 \(O(n)\) 个字符串，每个字符串可以描述为两个字符串的子串拼起来，然后用二分哈希比较就可以了。
场上拼串的时候多弄了一个字符， \(90\)。
T3
暂时还不会
T4
考虑建图，图本身很类似一棵树，因为合法括号序列本身就是树的结构，将一对括号视作树上的一个节点，这个节点中含有两个子节点，那么连边就是一个节点中的两个子节点连边以及儿子的左右两个子节点之间连边，以及最左最右的儿子向对应的父亲子节点连边。
然后任何路径必须在 LCA 处交汇，变成树上路径问题，可以倍增。
注意因为我们实现的时候建了一个虚拟节点，实际上不能走它，需要特判。