B

给序列 $a$ 和 01 序列 $b$ ，三种操作

1. 单点修改 $a_{t1}=t2$
2. 给 $b$ 的 $[t1,t2]$ 区间加上 $1$
3. 询问一个区间 $[l,r]$，对于 $a$ 序列，找这样一个下标的集合，先把 $l$ 加入，然后每次在序列中，找下标集合中最大的元素的右边的且在区间内的大于等于该下标元素的第一个数，把他加入集合，如果找不到就结束这个过程。输出这个得到的下标递增集合在 $b$ 序列中的有多少相邻数满足 $b_{p_{i}} \neq b_{p_{i+1}} \mod 2$ 。

线段树经典 $log \space update$ 问题？

意思就是说除了普通的线段树区间操作，所要维护的信息还需要进一步递归的继续获得。

前置题目 P4198 楼房重建

发现这两题非常的类似，都有对一个序列递增的要求，这题唯一的不同就是还需要维护一个对应下标的 b 序列切换的答案。

设一个区间中满足题目要求的答案是 $ans$， 我们可以在线段树上用递归来求。

考虑一个区间 $[l,r]$ 的答案，他的左区间是 $[l,mid]$，那么左区间的所有答案一定必须成为当前区间的答案，只需要考虑右区间在受限于左区间的最后一个取的东西，也就是最大值来继续取。

对于右区间，显然的剪枝是若这个区间最大值已经更小了，就不可能有扩展的答案了。

然后继续分治递归。

1. 若右区间的左区间的最大值能继续延申，那么递归左区间，同时这个左区间的最大值一定能被取得，可以利用已有信息直接算出把右区间的右区间的贡献。
2. 若右区间的左区间不能延，只需要递归右区间即可。
3. 在叶子结点，按照题目条件判断即可。

然后就做完了。

对于修改，只需正常的线段树修改操作。

对于询问，因为每次都是重新取，可以先取个左界，再把线段树上剩余结点拿出来求一遍。

线段树上一次修改询问最多 $log$ 个结点，信息从下合并上来最多递归 $log$ 层。

复杂度 $O(nlog_2n^2)$。

E

$n$ 堆石子，两人玩类似 $nim$ 的博弈，每次取的数可以是 $mu[x]=1$ 的数或者是给定的至多 $5$ 种数。每堆石子的范围是介于 $[l_i,r_i]$ 的数，需要输出所有的 $\prod r_i-l_i+1$ 种方案中，有多少种方案先手必胜。

$n<=10^6$， $1 \leq l_i \leq r_i \leq 10^5$。

首先，可以考虑打表打一下 $sg$ 。

发现 $sg$ 没什么规律，且值域不大。因为取的数 $mu[x]=1$ 其实也没什么规律，出题人说最多值域到 $230$ 。

如果能打表出到这个类似的数字，考虑优化转移求 sg 的过程。这个可以用 bitset 简单的做到。

设 $trans[i][j]$ 表示 $j$ 是否存在 $sg$ 值为 $i$ 的出边，这样枚举 $j$ 就能方便的求得他的 $sg$ ，且更新对应 $trans[sg[j]]$ 数组 ，所有的别的数都可以通过取 $j$ 来得到 $sg[j]$ 。

1
2
3
4
5

    trans[0] = pick;
    for (int i = 1; i <= 100000; ++i) {
        while (trans[sg[i]][i]) ++sg[i];
        trans[sg[i]] |= pick << i;
    }

这样复杂度是 $O(\frac{n^2}{64})$ 的。

剩下的部分，就相当于要求所有异或和不为 $0$ 的方案，这个按照套路可以用 $fwt$ 来求，但两个序列的异或情况好求， $n$ 个序列无法一一做变换最后再乘起来。

考虑所做的数都是一些连续的数，可以用前缀和来求，考虑直接求出 $fwt$ 异或变换后数组的前缀和，这样对于每个 $[l_i,r_i]$ 直接乘起来就是对的，因为是 $fwt$ 异或变换后的数组了。

然后这里还需要知道 $fwt$ 异或变换在干嘛，不然也不能做

$$ A_i =\sum_{C_1}A_j-\sum_{C_2} A_j $$

其中 $C_1$ 表示 $i\And j$ 奇偶性为 $0$ ， $C_2$ 表示 $i\And j$ 奇偶性为 $1$，如果当前下标与变换后下标 $i$ 与运算是偶数个 $1$ 则加，否则减。

于是就可以在 $O(100000*256)$ 算出 $sg$ 值变换后的前缀和，最后只需要 $fwt$ 乘起来即可。

复杂度 $O(\frac{n^2}{64}+(n+100000)*256)$

J

$n$ 个点， $m$ 条边的有向图，求 $floyd$ 算法 和 三重循环最后枚举中间点的算法最短路 $dis$ 数组有多少对依然正确。

K

给一个序列 $a$ ，每次可以任选一个区间进行区间 $\mod k$ 意义下的 $+1$ 或者 $-1$，每次询问一个区间，最少需要多少次将所有数都变成 $0$。