【题解】牛客挑战赛46

T1 奇怪的计算器

按顺序扫过去，把每个数抠出来，然后先把连续的异或操作算出来，然后从左到右加减即可。

时间复杂度

T2 最小的指数

暴力枚举所有的 ，算出指数min，记除去这些质因子剩下的数为 。

对于 ，指数一定 。

• 若指数min ，显然 ，只需检验 即可。
• 若指数min ，显然 ，只需检验 即可。
• 若指数min ，显然 或 ，所以依旧只需检验 即可，注意需要满足 不是完全平方数，否则这个其实是指数min=4 。

时间复杂度 ，常数 左右。

参考代码

T3 排列

先考虑如何处理长为 ，逆序对数 的排列数。

用 表示长为 逆序对数为 的排列数，则考虑新加入 新增的逆序对数，

有 ，发现第二维是连续的区间，可以前缀和优化到 。

回到本题，超级逆序对要求 ，我们发现唯一的困难就是无法判断 和 的位置关系，所以考虑新加入一维。

用 表示长为 超级逆序对数为 且数字 的位置在 的排列数。

转移可通过比较 的位置和 得到类似上述的 转移式，前缀和优化即可优化到 。

时间复杂度

空间复杂度

参考代码

T4 数列

判断区间 是否满足条件，等价于判断 和 中每种数出现次数差是否都是 的倍数。

因此只需要计算每个前缀的答案即可，但发现并不是特别好维护。

考虑哈希，对于数 赋一个随机哈希值 ，记 表示 出现的次数模 ，则前缀哈希值 。

加上 unordered_map 即可做到 ，不放心的话也可直接 map 做到 。

时间复杂度 或

参考代码

T5 反演

其中 ， 。

本题即求

由于 ，所以可行的 只有 个，逐一枚举即可。

复杂度

参考代码

T6 柠檬树

的做法：

若要使 内的点两两连通，则将这些点按照 序排序后

（记为 ，满足 ），答案即为 ，其中

考虑将询问离线跑莫队。

对于区间从 到 ，其实只有一个新的点 插入了 序列中，显然是可以用 维护的。

每次插入，不妨设 ，则 要减去相邻两边的 ，并加上两个新的 。

区间从 到 删除时类似。

的做法：

答案即为 内的点到根的链并减去 到根的链长，不难发现前面这部分可以用 简单维护，即可做到 。

存在 的做法，搬一下lxl的原话（orz lxl）

直接启发式合并一下，维护子树和子树补的两两极近匹配，这样 个点 次查询的矩阵数点，考虑前驱后继用 维护，然后一个多叉树平衡。

因为修改 次，搞一个 深度 叉的树，就可以做到 了。