5 月做题记录

why nobody teach me chunithm || tornado please teach me asap || because tornado is too loong
	-- R216376593

P8582 斑马王子 Mas

题目大意

有一长度为 的数组 ，下标依次为 到 ，初始时有 。
接下来给定 个非负整数二元组 ，记 ，将所有符合 的 赋值为 。
在任意时刻，记 。接下来给定 个非负整数三元组 。

当 时，求：

$$t_i = \sum\limits_{x = a_i}^{b_i} \min\limits_{y \in S}(x \oplus y)$$

当 时，将所有符合 的 赋值为 。

当 时，将所有符合 的 赋值为 。

符号 表示全体整数， 表示异或。

，，，。

解答

看到异或，可以想到 Trie。我们记录一个状态 。因为每一个点都维护的一个区间嘛，当该点的 时，这个区间的点就至少有一个没有被删，否则就是全被删了。这个 是好维护的。

接下来我们对于每一个区间，维护当只有这个区间的数，不存在其它数时，的最小异或和 。现在该如何从下往上合并 ？很明显，当两边的 均为 时，直接加。当一边为 一边为 时，最优解法肯定是把 那边的移到 去。也就是 。

然后就是线段树区间查了。依然的，会被分成 个区间，如果查到了某一个区间的 为 ，那么它旁边就必须是 （因为是从上往下第一个 ）。那么就把查询区间平移到 那里去，再加上异或上 的贡献。如何平移？我们设零区间为 ，查询区间为 ，要想把现在的区间平移到 ，就把 分别加上 即可。查到每一个 区间后计算答案，最后合并。

K-D Tree 专题

 

插头 DP 专题

不想多说什么，看这里。

P1713 麦当劳叔叔的难题 Ult

被小朋友们贺的最惨的一道题。

题目大意

给定一个 的矩阵，和 个障碍，求出从左下角到右上角的最长距离和最短距离的差，要求每次只能上下左右移动，每一个方格只能走一次，障碍只能绕过。

，，。

解答

首先上下反一下矩阵就可以使起点在左上角，终点在右下角。最短距离用 BFS 就可以解决。现在求最长距离。

同样也可以使用插头 DP，每一个状态维护到达这个状态所需要的最大的格子数。还是用最小表示法 + 十进制表示状态。

1. 对于 ，只能有两种情况，向右的插头和向下的插头。
2. 对于障碍，若存在上、左插头为 的状态，就可以转移。

3. 对于中间的没有障碍的点，继续细分：

   1. 若当前状态存在向左、向上的插头，只有在不是一个连通块的情况下可以合并，否则就形成回路了。
   2. 若两个中只存在一个，既可以向右走，也可以向下走；
   3. 若两个都不存在，那就一是可以右、下插头都存在，二是可以右、下插头都不存在。

4. 对于 ，取两种只有一个插头的情况的最大值 。

注意状态要开 long long！否则就会和我一样以为是哈希出了问题花老长时间手写到一半才发现有一个状态是用 int 表示的……

P5445 [APIO2019] 路灯 Mas

题目大意

一辆自动驾驶的出租车正在 Innopolis 的街道上行驶。该街道上有 个停车站点，它们将街道划分成了 条路段。每一路段都拥有一个路灯。当第 个路灯亮起，它将照亮连接第 与第 个站点的路段。否则这条路段将是黑暗的。

安全起见，出租车只能在被照亮的路段上行驶。换言之，出租车能从站点 出发到达站点 的条件是：连接站点 与 ， 与 ，……， 与 的路段都被照亮。

在经过一些意外故障或修理之后，街道上的路灯可能是亮起的，也可能是熄灭的。

现在给定 时刻时，街道上路灯的初始状态。之后 时刻，每时刻会发生下列两种事件之一：

• ：切换第 个路灯的状态。具体地说，若路灯原来亮起，则现在将熄灭；若路灯原来熄灭，则现在将亮起。

• ：出租车部门的负责人想知道，从 时刻起到当前时刻，有多少个时刻满足：出租车能够从站点 出发到达站点 。

请你帮助出租车部门的负责人回答他们的问题。

对于全部数据，，，，。

解答

我们用 set 结构来维护连通性。最开始的状态就先用 set 预处理好。

然后我们现在要维护的是 在之前连通了多少个时刻。这个可以将其转化为二维平面问题，点 上维护的答案就是 在之前连通了多少个时刻。

首先是 toggle 事件，设当前事件编号为 ，即切换路灯状态，无非就是把两边的站点连通或者切断。若连通了 和 ，那么就使矩形 加上 ，否则若切断，则使矩形减去 。并且在 set 上更新状态。

然后查询，就单点查即可。注意，若此时 连通，则要把答案减去 。

矩形加、单点查，可以使用树套树。绝对不是因为我写不来 CDQ 分治 qaq

P5608 [Ynoi] 文化课 Ult

题目大意

Chimuzu 手上有一个数字序列 和一个运算符序列 。其中 只能为 或 。

我们定义一个区间 的权值 为将字符串

$$a_{l}~p_{l}~a_{l+1}~p_{l+1} \cdots a_{r-1}~p_{r-1}~a_{r}$$

写下来之后，按照运算符的优先级计算出的结果。

下面给出一个运算的例子：

若 ，，那么有：

$$w(1,6)=1+3\times 5\times 7+9\times 11=205$$ $$w(3,6)=5\times 7+9\times 11=134$$

Chimuzu 需要你对这两个序列进行修改，同时查询某个给定区间的权值。

你需要维护这 个操作：

操作一：给定 ，将 全部修改成 。

操作二：给定 ：将 全部修改成 ， 表示 ， 表示 。

操作三：给定 ：查询 的值。

对于 的数据，，， 均为奇数，，，所有操作 还满足 。时限为 1.5s

解答

这道题是一个死人线段树。

先分步走。

1. 没有修改的情况

在线段树上维护每一个节点 的左边连乘的答案、右边连乘的答案和这个节点最右边的符号。然后使用线段树 pushup 分情况维护即可。

1. 只有修改符号的情况

那么就再维护一个这个区间内所有数的加和和所有数的乘积，以及一个 lazytag。修改符号的时候就区间赋为加和或者乘积。然后修改那个最右边的符号即可。不要忘了 pushdown 操作！

1. 加上修改数值的情况

这种情况就比较麻烦，这里还要维护所有的连乘段的长度和一个修改数值的 lazytag。

因为本质不同的连乘段长度只有 个，所以可以使用 vector 来维护连乘段的长度和有多少个这种连乘段。然后修改数值就可以快速修改了。（虽然感觉时间复杂度是 就是了，空间复杂度也是对的。）

P2825 游戏 Mas/P10945 Place the Robots Mas/P6062 Muddy Fields G Exp

题目大意

在 2016 年，佳媛姐姐喜欢上了一款游戏，叫做泡泡堂。

简单的说，这个游戏就是在一张地图上放上若干个炸弹，看是否能炸到对手，或者躲开对手的炸弹。在玩游戏的过程中，小 H 想到了这样一个问题：当给定一张地图，在这张地图上最多能放上多少个炸弹能使得任意两个炸弹之间不会互相炸到。炸弹能炸到的范围是该炸弹所在的一行和一列，炸弹的威力可以穿透软石头，但是不能穿透硬石头。

给定一张 的网格地图:其中 * 代表空地，炸弹的威力可以穿透，可以在空地上放置一枚炸弹。 x 代表软石头，炸弹的威力可以穿透，不能在此放置炸弹。# 代表硬石头，炸弹的威力是不能穿透的，不能在此放置炸弹。例如：给出 的网格地图 *xx*，这个地图上最多只能放置一个炸弹。给出另一个 的网格地图 *x#*，这个地图最多能放置两个炸弹。

现在小 H 任意给出一张 的网格地图，问你最多能放置多少炸弹。

（注意 P6062 的题目描述比较不一样）

解答

这道题的意思就是，每一行（这里被硬石头隔断的同一行算两行）只能最多被选一次，每一列也最多只能被选一次。那么我们就对行和列建出二分图，是空地就连边，否则不连边，然后跑最大匹配即可。

然后 P6062 的就是二分图的最小点覆盖问题了，而根据 Ko上面两个点nig 定理，二分图最小点覆盖等于最大匹配的边数，于是可做之。

P3780 [SDOI2017] 苹果树 Ult

题目大意

夏天近了，又到了恋爱的季节，小 Q 家门前的苹果树上结满了红红圆圆的苹果。

这株苹果树是一个有着 个结点的有根树，其中结点被依次编号为 至 。 号结点为根，其余每一个结点的父结点一定是某个编号较小的结点。每一个结点上都有一些苹果，第 个结点上有 个苹果，每取走其中一个苹果就可以得到 的幸福度（若在这个结点取走 个苹果，则可以收获 的幸福度）。如果在一个结点取走了至少一个苹果，则必须要在其父结点处取走至少一个苹果。

现在，给定正整数 ，请从树上取走若干苹果。如果总计取走了 个苹果，且所有取了至少一个苹果的那些结点的最大深度为 （这里规定根结点的深度为 ），则要求 。问最大可以收获多少的幸福度？（这些幸福度全都归属于恋爱中的小 Q。）

本题有 组数据。

• 对于 的数据，满足 ；；；；；。

解答

就相当于是，你可以免费选一条链，这条链上的每一个点只能选 1 个，然后再做背包。

那么就可以把每一个点拆分为两个点 和 ，点 上只存 个苹果，然后剩下的 个苹果就存在 点里面。然后 和 连边，然后原边就在 上连。

这样我们选的那条最长的链的端点就只需要当它的 就行了。

这条链把整棵树分为了左右两半，那么我们就正着做一遍 DP 然后倒着做一遍 DP，然后枚举链的端点即可。因为要使被这条链分割出来的树的两半连续，所以就不能使用普通的 DFN 序，而是使用跳栈顺序（即后序遍历顺序）。后缀同理。

具体来说这个 DP 啊，我们设 为前缀 选了 个苹果所可以获得的最大的幸福度。因为选了一个点也必须要把它的父亲选上，所以我们可以设计 DP 转移式：

1. 当不选这个点时，子树都不能选，即 。
2. 当选了这个点时，子树可选可不选。那么就枚举这个点选了多少个苹果。即 。然后取最大值。

后缀同理。

最后枚举链然后取前缀最大值、后缀最大值再加和作为这条链的答案，然后取所有链的答案的 即可。

P10060 [SNOI2024] 树 V 图 Mas

题目大意

你有一棵 个点的无根树，节点的编号为 。定义树上两点之间的距离 为树上 点到 点的简单路径上的边数。

现在有 个关键点 ，对于每个点，我们想求出距离它最近的关键点是哪个点。也就是对于一个点 ，令 表示令 最小的 ，如果有多个 满足条件，那么我们会选择其中最小的 。

现在，我们给出了 ，问有多少组可能的 满足条件。由于答案可能很大，输出对 取模的结果。

对于所有的数据，保证 ，，。

解答

首先我们判断合法性。每一组拥有相同的 的点一定都是一个连通块。若不是，则直接输出 。

然后因为这道题 ，并且是在树上计数，所以可以使用一些暴力的树形 DP 做法。我们先把所有拥有相同颜色（这里指 ）的点缩起来。

设 为颜色 的关键点取 时，这个点的子树取点的方案数。当我们枚举点 的时候，我们要对每一个儿子检查一下这个是否合法。具体来说，是检查原树上，两个颜色的边界到 的距离，和边界到儿子的关键点的距离的大小关系。若合法，那么这个儿子的关键点可取。否则不可取。我们可以使用欧拉序 LCA 来 获得距离。这样时间复杂度就是 的了。

最终答案就是根颜色（）的 。

P5391 青染之心 Mas

题目大意

Cirno 初始有一个空的物品序列，一个大小为 的背包，现在你有 个操作，分为两种：

• add x y：表示加入一种体积为 , 价值为 的物品到序列末尾。
• erase：表示删除序列末尾的物品。

在每个操作结束以后，你需要求出：

假设序列中的每种物品都有无穷多个，Cirno 的背包可以装下的物品最大价值和。

对于 的数据 。

解答

建一棵操作树。树上每一个节点记录新插入了哪一个物品。

然后就可以开始 DFS。边 DFS 边完全背包 DP。对于一个新点，就让他对父亲那个版本做一遍背包 DP。

但是这道题它卡空间，那么就当这个点只有一个儿子的时候，就不新建版本了，直接在原来的版本上做。可以省空间。

P9058 [Ynoi] rpmtdq Ult/P9678 Tree Distance Ult

题目大意

给定一个无根的加权树 ，其顶点为 。请回答一些查询。

我们定义 为顶点 和顶点 在树 中的距离。

对于每个查询，给定两个整数 。请回答以下值：

$$\min_{l\le i< j\le r}(\texttt{dist}(i,j)).$$

解答

对于树上的路径 + 支配点对问题，我们可以使用点分治。

所谓支配点对，就是最关键的点对，其它点对都可以被支配点对支配，而弱于支配点对。就比如说有三个点 ，若 ，那么点对 无用，只考虑 。支配点对可以大大减少你需要考虑的点对的数量。

设当前的分治中心为 ，我们把所有的点分治的点拎出来，然后按照下标给它们排序。令点 的 为 。然后根据支配点对的性质，一个点的支配点对有 对，分别是左边第一个权值比它小的点，和右边第一个权值比它大的点。使用单调栈，跑两遍找到就行。

现在找到了 个支配点对，然后就可以开始处理询问了。问题现在变成了一个二维偏序问题，这个可以使用扫描线 + 树状数组做。

P6199 河童重工 Ult

题目大意

给定两棵树 。以及一个完全图，这个图上边 的边权为 。求这个完全图的最小生成树。

解答

树上点对距离，考虑点分治。

我们对 进行点分治，设这次的点分治的分治中心为 。那么令 。把每一次点分治出来的点搞到 上，建一棵虚树。

这时的在新图上的两点 之间的距离为 。

考虑把 和 放到那棵虚树上，就相当于是新增了两个点 和 。然后从 至 连边 和从 至 连边 。这样就成功地把考虑的对象只转化为那棵虚树了。

之后我们肯定想要对每一个 找一个距离 最近的点，但是又要保障图连通，所以我们对于虚树的每一条边的两个端点 ，分别找到距离 最近的新增点 和 ，然后就可以把 加入备选边里面。每一个点的对应点可以通过 Up and Down DP，第一次从下到上（即考虑该点子树），第二次从上到下 DP（即考虑非该点子树）求得。

最后你就有了 条边，然后使用 Kruskal 算法即可求得答案。

P5025 [SNOI2017] 炸弹 Mas

题目大意

在一条直线上有 个炸弹，每个炸弹的坐标是 ，爆炸半径是 ，当一个炸弹爆炸时，如果另一个炸弹所在位置 满足：
，那么，该炸弹也会被引爆。
现在，请你帮忙计算一下，先把第 个炸弹引爆，将引爆多少个炸弹呢？

答案对 取模

，，。

解答

线段树优化建图板子题。因为是求这个点可达的点的个数，所以考虑建有向图，连边因为是一个点向一个区间连边，所以就要使用线段树将边数优化到 级别。

之后就跑 Tarjan 缩点，然后使用 bitset 求可达性即可……吗？空间限制 ，你会死亡。

注意到一个炸弹炸到的区间肯定是连续的，所以只需要记每一个炸弹可以炸到的左端点和右端点即可。

P9260 [PA2022] Miny Ult

题目大意

给定一棵树（无向无环图），树上每条边有一个确定的长度。每个点上都有一颗地雷，每个地雷有一个确定的爆炸半径。如果一个地雷爆炸了，所有距离这颗地雷不超过其爆炸半径的地雷都会爆炸。我们定义两个点之间的距离是这两个点之间简单路径上边的长度和。对于每颗地雷，如果手动引爆它，确定有多少地雷会爆炸。注意对于每颗地雷，我们认为手动引爆它与手动引爆其他地雷互相独立。

解答

卡常等级：Past

树上「炸弹」，但思路和炸弹有所不同。

因为是树上距离问题，我们可以使用点分治。

对于每一个分治中心 ，先把所有点全部拿出来，然后按照 （到分治中心的距离）从小到大排序，然后开始连边。

发现这样连出来的边会是一个前缀，所以可以使用前缀优化建图，每次连边的时候二分那个前缀就可以了。为了不让那些虚点那么多，所以只存有用的虚点。无用的就不存了，既省时间又省空间。

然后就 Tarjan，但是这道题就没有像炸弹那么优美的性质了。所以只能用 bitset。但是为了防止卡空间，所以这道题只能用分组 bitset。即循环 次，每一次处理 个点的连通性。

莫队二次离线专题

P5047 [Ynoi] Yuno loves … Ⅱ Mas/P4887 莫队二离 Mas

莫队二离板子，不用多说。

P5398 GOSICK(第十四分块) Ult

题目大意

给你一个长为 的序列 ， 次询问，每次询问给一个区间 。

查询 ，且 是 倍数的二元组 的个数。

对于 的数据，，。

解答

卡常等级：Present

第一眼会想到莫队。我们计算每次移动时的贡献。

设 为 内有多少个数为 的倍数， 为 内有多少个数为 的因数。令 。众所周知的，移动分 种情况：

• 。
• 。
• 。
• 。

对于 和 项，我们可以将其预处理，然后莫队第二离线解决。现在来看其他的 项。

首先是 ：这个是好解决的，我们可以开一个桶， 表示 这个数 是多少个数的因数，即有多少个数是 的倍数。然后就离线、扫描线做就行了。时间复杂度 。

然后就是难缠的 ，要把这个东西做出来就必须要意识到：莫队二离的总区间个数是 个，并且区间的总长度为 。

根据根号分治（这里令 ），若 ，那么可以再维护一个桶，暴力跳倍数，这样最多 。

否则 ，那么这样的 最多也就只有 个了。我们枚举 ，然后遍历所有的 个区间：对于每一个区间 （这里的意思是 ），我们要计算 里面有多少个 的数，并且 里面有几个数为 的倍数，那么它对答案的贡献就是前者乘以后者。二者均可以先预处理为 0-1 数组，然后算前缀和就可以求前者和后者了。

最后算出来所有的 了之后，就前缀加，然后转移到真正的 数组上，输出即可。

然后就开始愉快的卡常时间！

首先，合并 的二离和 内 的二离。这会使常数减小。

然后，将询问的 vector 改为数组加上 cnt，并且按照关键字 p 来排序。这样亦可以减小常数。

并且，也可以使用循环展开 #pragma GCC unroll 8 来优化常数（但是这种在考试禁用，考试时只能手写循环展开）。

然后是重头戏：抛弃根号分治但保留思想，使用估价函数分治。我们使用估价函数来确定每一个值是使用第一种方法还是第二种方法的时间复杂度更优。

这样可以卡至 20 秒！最优解榜单排在 @Wjwweiwei 和某位提交了一百万次的私募匿名用户之下。

P4688 [Ynoi] 掉进兔子洞 Mas

题目大意

一个长为 的序列 。

有 个询问，每次询问三个区间，把三个区间中同时出现的数一个一个删掉，问最后三个区间剩下的数的个数和，询问独立。

注意这里删掉指的是一个一个删，不是把等于这个值的数直接删完，比如三个区间是 ， 与 ，就一起扔掉了 个 ， 个 ， 个 。

，，，，，。

解答

首先，先不考虑空间限制。

区间维护问题而且还是一道 Ynoi考虑莫队。

当每一个数都不同的时候，就先离散化，我们可以存一个值域 bitset，该位为 1 就说明这个区间中有这个数。然后 3 个区间的话其实不用管，把这 3 个区间拆开，然后对于每一个区间记录它属于哪一个询问，当跳到那个地方之后就和 bitset 与起来即可。最后求 popcount（即 .count()）即可得到答案。

而当有相同的数的时候，我们就要让离散化的方法有些许不同。我们要考虑那些一样的数，所以原序列 1, 1, 5, 5, 8, 8, 15, 15 应离散化为 1, 1, 3, 3, 5, 5, 7, 7。然后在莫队的时候记录一个 数组，当新加一个数的时候要插入 bitset 的数就变成了 ，然后让 自增。同理，删除的时候就先让 自减，再从 bitset 中删除 。

将空间考虑进来，若要在 内实现 的 bitset，就至少都要将询问拆成三份变成 的 bitset，此时空间足够，足以通过此题。

P4604 [WC2017] 挑战 Ult

题目大意

1. 任务一

给定 个 位无符号整数，将它们从小到大排序。

1. 任务二

有 个人在玩 「石头剪刀布」 游戏。他们排成两排，每排 个人。每个人在每一局游戏都使用固定策略，即对于第 排的第 个人，用一个整数 表示他的策略，其中 表示只出石头， 表示只出剪刀， 表示只出布。

现在有 个询问，每个询问给定三个整数 ， 问将第一排的第 个人和第二排的第 个人比赛之后，第一排有多少个人会赢。

上文中 「比赛」 的意思是，对于所有整数 满足 ,让第一排的第 个人和 第二排的第 个人进行 「石头剪刀布」 游戏。

1. 任务三

我们称一个合法的括号串为：只由左括号和右括号构成，两种括号的数量相等， 且任意一个前缀的左括号数量不少于右括号数量的串。现在给定一个由 (，) 和? 构成的串，问有多少种不同的方案，使得将每个 ? 都替换成一个括号之后，该串变成一 个合法的括号串。两种方案不同，当且仅当至少有一个位置的 ? 被替换成了不同的括号。

注意以下数据范围：

对于任务 1，，时限 6s。

对于任务 2，，时限 3s。

对于任务 3，，时限 3s。

解答

这道题其实是一道究极无敌（其实也没那么无敌）卡常题。

---

对于任务 1，平常的排序算法其实都不适用了。要一个时间复杂度接近于 的排序算法，我们想到的就只有计数排序和基数排序。使用计数排序的话值域太大不行，只能使用基数排序。

平常的基数排序是以 为底，所以复杂度为 ，而这道题 且 ，所以极难通过。所以只能更改底数，因为值域范围为 整数，所以考虑每次均以 为底，排序 次，这样时间复杂度就为 了。可以通过，且无卡常。

---

对于任务 2，一个朴素的想法就是使用 bitset 来存储石头有哪些人出、剪刀有哪些人出、布有哪些人出。然后两排都开，就有 6 个 bitset。然后每一次就取出两边的 位，然后将它们与起来，再计算 popcount 即可。

但是 STL 的 bitset 不支持取出位区间操作，所以这里使用手写 bitset。

在手写 bitset 中，以 64 位为一个 unsigned ll，即一个块，然后维护 个块。取出位区间是可以写的，但是这样非常的麻烦，这是因为一个区间 可能会包含 个散块，并且它们对不齐。

为了让它们的开头都为整块的开头，我们再维护当前 bitset 全局左移 1 位、2 位、3 位……一直维护到全局左移 63 位的结果。这样，假如说一个区间 在开头第 位，那么访问左移 位的结果，就可以使这个区间的开头为整块的开头了。然后再与，最后的散块 暴力或 处理均可。

这样，时间复杂度为 ，空间复杂度为 。卡常重点在手写 bitset 上，所以轻微卡常。

---

对于任务 3，朴素做法是做 DP，我们令左括号 ( 为 ，右括号 ) 为 。设 为目前前缀和为 的方案数。那么初始设 ，然后转移：

• 当 ，全局 。
• 当 ，全局 。
• 当 ，全局 。

暴力做法显然过不了，但是左括号和右括号可以视为偏移操作，所以这里使用指针。

令当前指针为 beg，那么当 ( 时就让其往左偏移，使 beg --。（注意此时要让 beg[0] = 0）当 ) 时就让其往右便宜，使 beg ++。而当为 ? 时，就可以先让指针往左偏移，然后令所有的 beg[j] += beg[j+2]。但是这样明显过不了，就要开始无穷无尽的优化了。

首先，当前有贡献的区间就只有 。因为你前面就是加左括号，然后后面肯定是要加右括号圆回来。然后，发现每一次有值的下标不是全部奇数就是全部偶数。因为每一次指针自增自减明显不影响，只是从全奇和全偶转换。然后 beg[j] += beg[j+2] 也不影响其性质。所以只用枚举奇数位或者偶数位即可。如何判断是枚举奇数位还是偶数位？容易证明当 为奇数（这里为 ）时枚举偶数位， 为偶数位时枚举奇数位。

时间复杂度最坏 。平均数据下可以跑过，最坏数据下给 beg[j] += beg[j+2] 加一个循环展开可以通过。比较卡常。

P5313 [Ynoi] WBLT

题目大意

给你一个长为 的序列，有 次查询操作。

每次查询操作给定参数 ，需输出最大的 ，使得存在一个 ，满足 ，使得 都在区间 内至少出现过一次。

如果不存在 内的数，则输出 。

对于 的数据，所有出现过的数在 之间。

解答

想法是比较好想的。我们记录一个 bitset 表示每一个值域有无出现过。

当 时，就可以暴力使用 bitset 位移：记录一个大小为 的新 bitset，最开始里面全是 。第一次，将下标 的 bitset 和新 bitset 按位与（结果存到新 bitset 里），然后检查这个新 bitset 是否含 。若没有则退出。然后第二次就将下标为 的 bitset继续和新 bitset 按位与……一直到不含 为止。

当 时，就可以对每一个 分治。对于每一个 ，我们开 个 bitset，代表余数为 的所有值有无出现过。 表示 有无出现过， 表示 是否出现过……然后答案就是每一个 bitset 的 值的最大值。

这两种操作用 STL 的 bitset 均无法通过（因为时间复杂度太大），所以这里使用手写 bitset。依然是使用 个 unsigned long long 存储。接下来就讲手写 bitset 的细节。

---

第一个要实现将一段区间 提取出并与到另一个的开头上。下图为我在思考时做的草稿：

这个草稿基本上模拟了将区间 （这里是 ，且块长为 ）与到另一个 bitset 上的全过程。首先就是提取出最左边的散块，记录 和 。 为这个区间在原序列的某个块内的最早出现位置， 即为第一个散块的长度。

然后后面整块就是 将整块拼起来。然后最后一个散块就特判和第一个散块的加起来长度和是否 即可。然后再根据这个分情况讨论。

---

而第二个实现的相对简单：即求一个 bitset 的 。这个使用普通的扫，若全 则跳过，否则就要求目标块的最前面有多少个 ，就先取反，然后使用 __builtin_ctzll() 函数求即可。

注：__builtin_ctzll 即为 builtin count-zero long-long，能在极短的复杂度内求出最低位有多少位连续的 。这里为了求最低位有多少位连续的 ，就先取反再使用即可。

---

这里设的 的阈值为 ，然后莫队还是一样的 优化。记得每一次对较小的 分治后要清空！