1108总结

线程阻塞

考试 考试的时候还很清醒，考完脑子就乱了。

大脑从 i7-9th 退化成 i3-4th，四个字来说就是线程阻塞。

如果说整个社会是一个计算机系统，那一个人自己的大脑就是主板上的所有部件，而其他人，则是一块块只读 HDD 中的数据。当某一块 HDD 损坏，不能存储数据，但是又不想丢失它，就只能将数据保存于主存。主存的大小是有限的，它本不是用来保存数据，如果占用过多，会影响主板部分的正常运行，受到内存大小的限制，CPU 的运算能力自然会退化。

我不太想找心理医生，心理医生会帮我清除掉主存的数据，但是我不想清除。

T1

AC 自动机

比较模板的 AC 自动机匹配题，但是 AC 自动机做法需要细算常数，这道题倒是将缓存行访问连续的重要性体现的相当清楚，可以参考几次提交的差异。

直接动态规划

另一种方式是注意到两个字符串互不影响，因为出现任何一个字符串都不会对另外一个字符串的出现产生额外影响，所以无需记录具体到了哪个节点。

先考虑没有限制的转移，如果为 ?，则乘 26，否则不变，这样有重复，唯一的重复是对于两种字符串如果接下来可以匹配上，那么转移就应该到对应的差值，因为两种字符彼此不包含所以两种字符串的重复可以独立处理，还是挺好写的。

T2

考场上发现本质上是个可以用线段树做的二维偏序，但是由于马拉车算法本身有二倍常数，还需要跑 4 遍，所以其实有点难卡常，感觉递归版的没救所以我写了非递归版的 update 操作勉强卡过去（query 次数不多可以直接查）。

但是这个答案是可以二分的，二分之后配合马拉车就是个 RMQ，ST 表即可。

T3

容易发现一定会在某个地方反复横跳刷分，所以处理出所有横跳位置的刷分函数（是一次函数），有用的一次函数级别为 \(O(n)\)，为了保证每个函数都可以正常取到，不妨暴力处理前面的 CASE，然后后面的就是维护凸包。

不处理前面的 CASE 是错误的，因为你不能保证在对应的步数限制下一定可以拿到这个函数。

感觉不预处理但是加上某些条件再筛一下函数就可以过，但是这些条件有点难想吧...

T4

少见的 mex 配 xor 题，考场上没想出来，现在脑子很乱，明天再想——11.8

mex 应该是个非常严格的限制，由于询问很少，所以考虑单个询问怎么解决。

比较暴力的方式是逐个加入元素并检查可行性，我们显然必须要求能构成一条链，所以加入点的过程其实比较简单，如果链已经是弯折的形式，那么只能在两颗子树内加点，如果不是，那么新加点和最较深求 LCA，如果在路径上则不合法，重新构造路径的过程也是平凡的。

考虑检查第二个条件，也就是异或合法性，路径的异或值是好求的，对于两边的情况，可以暴力遍历树枚举一边用字典树求另一边。

但是这样的复杂度不对，因为每次暴力遍历都是 \(O(n\log n)\) 的，一共进行了 \(O(nq)\) 次。但是认真思考一下发现答案是可二分的，所以二分即可，复杂度 \(O(nq\log^2n)\)。

\(10^5\) 的题和 \(3\times 10^5\) 的题，考虑复杂度的方式是完全不同的（\(10^5\) 基本可以扔进 L3），所以没必要担心。

好像不二分也是可以的，考虑答案的形式，因为一定会包含 \(0\)，所以以 \(0\) 为根后，可以取到的异或值就形如 \(d_u\oplus d_v\)，其中 \(d_u\) 表示 \(0\) 到 \(u\) 路径上的异或值，每次移动端点时，两边可选的 \(d\) 集合都在变化，集合变化次数是 \(O(n)\) 的，动态维护 \([l,r]\) 区间中数的个数就可以了。

注意，动态维护 lower_bound 的最小值是行不通的，因为最小值不具备逆元，是不可减的。