T1
过水已隐藏
T2
整体二分经典题，主席树上二分也可以
在二分时要算一个国家的每一个出现位置，看起来是不行的但是均摊一下没有问题
使用线段树辅助计算答案
T3
过水已隐藏
T4
裸的cdq分治三维偏序，但我现在还不会怎么cdq套cdq……
再高维的话就是二维数点的BIT了
可以用bitset并起来乱搞，复杂度\(O(\frac{n^2}{w})\)
xpp:四维往上就跑不过暴力了
T5
神奇妙妙题
我们用ST表先预处理一下区间流量最大的东西向道路和南北向道路
在分治之前，先处理出边界的最长距离为0，分治一开始的区间是整个矩阵
我们每一次先选出区间内流量最大的东西向或南北向道路，这代表如果其走入了这条路，不会拐弯，则这条路上的点的最大值就是其到边界两条路中大的那一条，边界的值都已经算出
然后这条线会把当前的区间分为两份，继续递归
主定理可得分治的复杂度为\(O(H+W)\)
总复杂度为\(O((H+W)Q)\)
代码细节较多
T6
直接二进制拆分，用ST表预处理
T7
这里我们可以暴力枚举子串的起点
利用字符串匹配的性质，其肯定有单调性，我们进行二分，不断的枚举下一个不同的位置
具体的实现等在研究研究再补
T8
水省
T9
我们可以建一颗后缀树和前缀树，分别跑匹配的前后缀
然后可以利用dfn序的性质，将一个点在前缀树上的dfn序作为横坐标，后缀树为纵坐标
则此题转化为了一个二维数点的问题，将两个子树dfn序的范围取个交，这点分类讨论就可以
然后再将询问离线下来，做扫描线即可
复杂度单log
T10
异或有自反性，这里可以维护一个节点到根的异或和f[i]
则节点 i 到 j 的异或路径和为f[i]^f[j]
将所有的f[i]一起建一颗 01trie,对于每个值贪心选取就行
复杂度线性带 30 的常数
T11
可以将柿子转化为\(\sum_{i=1}^{18} [f(a_{i}\, xor\, a_j)=i]*i\)
进一步可以推出\(\sum_{i=1}^{18} [f(a_{i}\, xor\, a_j)\geq i]\)
这里没乘系数，每一个数值会在小于它时多算，所以没有错
这样就可以在 01trie 上小DP一波了，我们枚举 \(10^i\) ，如果基准数当前位置上是 1 就只能走 1，若是 0 ，就把 1 部分的串个数加上，走 0
T12
kmp配合DP
我们定义f[i][j]为 s 走到了 i, t 走到了 j 的次数
如果 \(s_i=t_i\) 则直接转移，如果到了末尾，就答案加一
如果没有匹配，则我们与处理出来一个类似 fail 压缩的写法，找到当前 t 最长的有匹配的 border 进行处理
如果是问号，就枚举起边成哪个字符，用上方方法进行转移