11.16考试总结
总结
这次考试沿用了csp-s2的特性，题目难度乱序（准确的来说是倒序）。虽然我在看了最难的A一定时间后及时选择了放弃，但是我拿到题的时候没有选择先把题目全部看一遍这个失误非常严重，这样会使我缺少对一场考试的全局观，打乱我考试的布局，并且更容易使我意气用事死磕A题。虽然这次考试侥幸及时从A跳了出来，但是下一次就不一定了。考试经验不是用来放口头当摆设的，要实际用起来。
然后，看到区间与和脑子里应该首先想到对于一个固定的边界找它往左/往右第一个二进制位为0的地方，这是与所具有的为数不多的性质之一，一定熟记。
然后，对于区间问题，如果常规的log一类数据结构无法以正确的时间复杂度维护，那么就要考虑非常不显然的莫队/分块这种类似于乱搞但是能非常巧妙地降低时间复杂度地算法。
题目简述
A
给定一颗有根树，每次给出l,r,x询问有多少对a,b,满足l<=a<b<=r且LCA(a,b)=x。
原题DTOJ5021最近公共祖先
我直接搬部分题解过来算了
考虑将问题转化为：x的子树中在[l,r]之间的点对数，减去x的子节点的子树中在[l,r]之间的点对数（因为x的子节点一定是它的子树中在[l,r]之间的点对的公共祖先，所以最近公共祖先一定不为x）
前半部分很简单，直接使用主席树就可以了（这个稍微想一想就可以了，是基本的主席树）
主要是后半部分如何解决
有一个可以很容易想到的就是先重链剖分，然后就可以让重儿子按照上面的方式去算
对于轻儿子的话，没有什么太好的处理方法，所以考虑用莫队，l ll和r rr变化时，就让这个点一直沿着重链条就可以了
时间复杂度为
考虑怎么优化呢？刚刚的问题在于轻儿子可能很多，这大大增加了第二部分的时间复杂度，怎么办呢？我们考虑以为伪树剖，设置一个闸值P，对于所有size>P的子树，把它们都当做x的重儿子 这样，我们就可以减少轻儿子的数量，从而平衡两边的复杂度
B
给定一个长度为n的序列a(a[i]<2^30)，q次询问，给出l,r询问l，r区间内的全部序列a的子串的与和(全部&起来)去重后有多少个元素。
对于这种区间&的问题，我们应该第一时间反映到对于一个固定的边界，向左或者向右其每个二进制位第一个出现0的地方使会使其与和变化，由此也可以推算出询问的答案最大为n * 30(固定右边界，向左每个二进制位第一次出现0的地方是会使答案变化的地方，由于二进制只有30位所以每个右边界最多贡献30个不同的答案)。
受此启发，我们实际上可以找到很多小段(数量上限为n * 30)，其每个小段内任意子串与和的值都是一样的。但是可以注意到，如果[2,5]和[3,6]是两个满足上述条件的小段，那么在查询[2,6]时显然只会查到一个值，但是如果直接查询会查到两段，解决方法是将相邻有交集的两段用一根长度刚好覆盖两段且贡献为-1的长段加入数据结构中。本题强制在线，预处理段然后主席树即可。
CD较水且没什么新意就不说了