趣题摘记-算法题精选-2

这一系列文章记录了我遇到过的一些 趣题。

文章内容	简介
奇思妙想	数学和计算机领域，通过小小思考后能豁然开朗的趣题。
概率和期望	数学和计算机领域，与概率和期望相关的趣题。
算法题精选-1	OI/ICPC 向的算法题，去其琐碎、留其精髓，望博君一笑。
算法题精选-2	OI/ICPC 向的算法题，相比上一期题意更简洁，出处往往不可考。

按机器得金币

题意：有 $n$ 台机器。第 $i$ 个机器在前三次被按下时，分别掉出 $a_i,b_i,a_i$ 个金币，第四次开始不会掉金币。对于每一个 $k=1,2,\dots,3n$ 都要询问：如果按正好 $k$ 次，最多能掉出多少金币。$n \le 10^5,v \le 10^9$

题解：每个机器的选择之间有限制，不利于分析。一台机器的四阶段顺序事件 $(0,+a_i,+a_i+b_i,+2a_i+b_i)$，可以 等价于 两个独立的金币掉落事件（$a_i,a_i+b_i$），即后者的 $2^2$ 个状态正好对应前者 $4$ 个阶段。现在条件就转化成：有 $n$ 个代价为 $1$，收益为 $a_i$ 的事件；以及 $n$ 个代价为 $2$，收益为 $a_i+b_i$ 的事件。从大到小排序后贪心即可，要不加入一个代价为 $1$ 的事件，要不弹出一个代价为 $1$ 的事件并加入一个代价为 $2$ 的事件。

有向图可达点的比较

题意：给出一个有向图（可能会有环），每次询问 $x$ 能到的点和 $y$ 能到的点谁比较多。保证每次询问满足两者的相对差值较大。$n,m,Q \le 5 \times 10^6$。From Claris。

经典定理：$k$ 个 $[0,1]$ 的随机实数的期望最小值是 $\frac{1}{k+1}$。

题解：注意有向图的准确可达点数量只能暴力（bitset）求。为每一个点随机一个 $[0,1]$ 的实数，$O(m)$ 求出每个点在可达点里的实数最小值 $\min_i$。询问时只需比较 $\min_x$ 和 $\min_y$ 大小关系即可。多随机几次打擂台。

区间平面最近点对

题意：平面上 $n$ 个整点，询问 $[l_i,r_i]$ 的平面最近点对（欧几里得距离最小）。$n,q \le 25000,|x_i|,|y_i| \le 10^8$。

来源：Ynoi2002 Adaptive Hsearch&Lsearch。

前置：期望线性的平面最近点对网格算法，可见 OI WIKI。假设前 $i-1$ 个点的最近点对距离为 $s$，以 $s \times s$ 的网格做平面划分，并把前 $i-1$ 个点都塞入对应的网格中。检查第 $i$ 个点所在网格的周围 $9$ 个网格并更新答案，注意到每个网格里最多落入四个点，所以需要检查的点数是 $O(1)$ 的。检查过程中，如果答案被更新就重构网格图。

前置复杂度分析：前 $i$ 个点中最近点对包含点 $i$ 的概率是 $O(\frac{1}{i})$，重构网格的代价是 $O(i)$，总复杂度 $O(n)$。

直接转化：把所有点分块，预处理出从任意点开始、每个块结尾的网格数据，查询时暴力插入前面零散的点。根据上述分析，每一次差点触发网格重构的均摊代价是 $O(1)$，所以总复杂度是 $O((n+q)\sqrt n)$。

标准做法：假设最近点对距离 $d$ 满足 $d \le s$，那么按 $s \times s$ 划分的网格能求出 $d$，但当 $d$ 过小时要检查的点数量过多。这启发我们按 $2^0,2^1,\dots,2^k,\dots$ 分别划分网格，$2^k \times 2^k$ 的网格负责解出 $2^{k-1} < d \le 2^k$ 的答案，小的 $d$ 由更小规模的网格求解，即我们可以在点数较多的格子里删至 $O(1)$ 个点保持时间复杂度。按编号从小到大加点，每个点会在每级网格里各贡献 $O(1)$ 个点，即 $O(\log V)$；插入点 $i$ 时，它和前面某些点会构成最近点对的判定，例如和 $j$ 的距离是 $dis(i,j)$，就在数据结构里插入这组贡献；当触发网格删点时，优先删除最先插入的点；插入点 $i$ 后，考察所有 $r=i$ 的询问，$l$ 的答案记为数据结构里 $[l,i]$ 的区间最小值。我们要支持 $O(n\log V)$ 次插入、$O(q)$ 次询问，分块复杂度为 $O(n \log V+q \sqrt n)$，树状数组复杂度为 $O(n \log V \log n+q \log n)$。

最大团

题意：$n$ 个点 $m$ 条边的无向图，求最大团的大小。$n,m \le 200$。来源：叉姐 2015 ICPC Camp。

题解：求最大团的经典方法是 Bron-Kerbosch 爆搜，复杂度为 $O(3^{n/3})=O(1.44^n)$，本题显然 $n$ 过大。

注意到 $m$ 很小，节点总度数只有 $2m=400$。取阈值 $d=20$，把所有点按度数分成大点和小点。

• 如果最大团包含至少一个小点。枚举小点，显然最大团集合必然属于该点的邻点集合，$O(2^d)$ 枚举验证。
• 如果最大团不包含任何小点。显然最大团集合必然属于大点集合，$O(2^{2m/d})$ 枚举验证。

综上，得到最大团的一种复杂度为 $O(2^{\sqrt{2m}}\cdot nm)$ 的分块爆搜做法。

强连通图删边

题意：$n$ 个点的有向强连通图，问选三条边删除使不强连通的方案数。 来源：2023 hdu多校 3C Leshphon。

题解：首先如何判断一张图是否是强连通？只需判断 $1$ 是否能到所有点，以及所有点是否能到 $1$。注意这个 BFS 可以从 $O(n^2)$ 优化到 $O(n^2/w)$。接下来考虑计数。如果图是强连通的，考虑之前遍历得到的两棵 BFS 树，显然所有树边中至少得删除一条才能使图不再强连通。在 $O(n)$ 条树边中任意枚举一条，然后递归成子问题。

假设删除 $k$ 条边，一共要递归 $k$ 层，每层 $O(n)$ 个子问题，底层 $O(n^2/w)$ 检查，总时间复杂度 $O(n^5/w)$

三维箱子的碰撞

题意：给出三维空间中 $N$ 个尺寸相等的长方体箱子，第 $i$ 个覆盖 $[a_i,a_i+L] \times [b_i,b_i+W] \times [c_i,c_i+H]$。判断是否存在两个箱子有公共部分。$N \le 10^6$。From Claris。

题解：将三维空间划成 $L \times W \times H$ 的格子单元，把第 $i$ 个箱子放入 $(\lfloor \frac{a_i}{L}\rfloor, \lfloor \frac{b_i}{W}\rfloor, \lfloor \frac{c_i}{H}\rfloor)$ 的格子中。显然一个格子里最多只能放入一个箱子，否则必然有冲突。然后枚举每个有箱子的格子周围 $6$ 个格子判断是否有交。

最长回文子串

题意：给出一个长度为 $N$ 的字符串。对它的每个前缀都求最长回文子串的长度。$N \le 10^6$。From Claris。

题解：令 $F_k$ 表示 $S[1\dots k]$ 的最长回文子串长度。有结论 $F_{k-1} \le F_k \le F_{k-1}+2$。每次扩展时，只要暴力 Hash 检查 $S[k-F_{k-1}-1\dots k]$ 和 $S[k-F_{k-1}\dots k]$ 是否是回文串即可。时间复杂度 $O(N)$。

(max, +) 卷积

题意：给出两个长度为 $N$ 的数组 $A,B$，求一个长度为 $N$ 的数组 $C$ 使得 $C_i=\max \limits_{0 \le j \le i}(A_j+B_{i-j})$。

$N \le 10^5$，$A$ 和 $B$ 的每一项都在 $[0, 10^9]$ 均匀随机。

题解：由于是 $(\max,+)$ 卷积，$A$ 和 $B$ 中越大的数越有用。取 $S=A$ 中第 $k$ 大的数 $+B$ 中第 $k$ 大的数。找出所有满足 $A_i+B_j \ge S$ 的二元组 $(i,j)$，更新 $C_{i+j}$ 的值。最后检查 $C$ 中的每一项：

• 如果它被更新过，那么已经得到了这个位置的最优解。
• 如果它没被更新过，直接按定义 $O(N)$ 计算它的值。

随机数据下，满足 $A_i+B_j \ge S$ 的二元组期望数量是 $O(k^2)$，概率为 $\int_0^{k/N} x \ dx=\frac{2k^2}{N^2}$。下面分析 $C[0\dots N]$（$C[N+1\dots 2N]$ 类似）。如果 $C_i$ 被剩下，那么它对应二元组均不满足条件，概率为 $(1-\frac{2k^2}{N^2})^{i+1}$。

按定义暴力计算所有剩下项的期望时间为：

$$\sum \limits_{i=0}^N (1-\frac{2k^2}{N^2})^{i+1}(i+1)=O(1/\ln^2(1-\frac{2k^2}{N^2}))$$

期望总时间复杂度为 $O(k^2+1/\ln^2(1-\frac{2k^2}{N^2}))$。为了最小化期望时间复杂度，有 $k^2=1/\ln^2(1-\frac{2k^2}{N^2})$。

$$-k=1/\ln(1-\frac{2k^2}{N^2}) \rightarrow -\frac{1}{k}=\ln(1-\frac{2k^2}{N^2}) \rightarrow e^{-1/k}=1-\frac{2k^2}{N^2}$$

把左式泰勒展开，有 $1-\frac{1}{k}=1-\frac{2k^2}{N^2}$，得 $k^3=\frac{N^2}{2}$，即 $k \approx O(N^{\frac{2}{3}})$，总时间复杂度约为 $O(N^{\frac{4}{3}})$。

木棒拼三角形全家桶

题意：$n$ 根木棒，长度分别是 $d_i$，从中选出三根使得拼成的三角形面积/周长最大/小。

周长最大：此题我曾出在 2018 百度之星A 第一题。考察最长的三根木棒 $(a,b,c)$，若 $a+b>c$ 则得到最优解，否则 $c$ 一定是无人企及的存在，删除它并递归处理即可。

等价于：对木棒排序后从后往前检查相邻三根，复杂度 $O(n \log n)$。

周长最小：对木棒排序后，设答案是 $d_i \le d_j \le d_k(i <j<k)$，从小到大枚举 $j$，显然 $k=j+1$。在左侧二分出 $i$ 使得 $d_i > d_{j+1}-d_j$，复杂度 $O(n \log n)$。

面积最大：枚举最长边 $c$。假设枚举了次长边 $b$，考虑旋转 $b$ 时能拼上去的所有的最短边 $c$。显然 $\angle C \le 90°$ ，所以 $c$ 一定越长越好。问题转化成：对木棒排序后，从小到大枚举 $k$，要快速找到最优的 $j$ 使得 $S(d_{j-1},d_j,d_k)$ 最大。考察相邻 $j$ 的面积，即 $S(d_{j-1},d_j,d_k)$ 和 $S(d_j,d_{j+1},d_k)$，用类似的推理可得后者必然优于前者。

等价于：对木棒排序后检查相邻三根，复杂度 $O(n \log n)$。

面积最小：此题我曾在 opentrains 一场比赛中做过，当时有额外限制 $n,\max{a_i} \le 10^5$ 且每一种长度不重复。当时的题解是：不妨设三条边 $a < b < c$，枚举 $c-b$ 的值 $d$。

• 假设已经知道了 $a$，三条边就是 $a, b, b + d$，显然 $a$ 固定时 $b$ 越小面积越小（证明：把 $a$ 这条边放在双曲线的两个焦点上，另外一个点正好落在双曲线上，面积与高度成正比，显然服从单调的关系）。
• 假设已经知道了 $b$ ，$a$ 显然越小越好（要保证 $a>d$）。

注意 $(a,b)$ 都是只和 $d$ 关联，彼此可独立考虑。所以枚举 $d$ 后 $a$ 和 $b$ 都能直接确定，其中 $a$ 是满足 $>d$ 的最小木棒长度 ，$b$ 是满足 $(b, b + d)$ 都存在的最小木棒长度。后者用 bitset 加速。复杂度 $O(\frac{n^2}{64} + n \log n)(n \sim V)$。

查找交集最大的一组人

题意：有 $n+1$ 个人，$2n$ 个物品。每个人正好喜欢其中的 $n$ 个物品。给出这些信息，找到某两个人 $(i,j)$，使得这两个人喜欢物品的交集的个数不小于 $n/2$，或报告无解。$n$ 是偶数且 $n \le 6000$。

结论：随机选一对 $(i,j)$，$E[|S_i \cap S_j|] \geq n/2$。

证明：设第 $i$ 个人认为的好物品集合是 $S_i$, 认为物品 $j$ 是好的人集合是 $T_j$：

$$E[|S_i \cap S_j|] = E[\sum_{k=1}^{2n} [k \in S_i \cap S_j]] = \sum_{k=1}^{2n} E[[k \in S_i \cap S_j]] = \sum_{k=1}^{2n} \frac{\binom{T_k}{2}}{\binom{n+1}{2}}$$

因为$\sum_{k=1}^{2n} |T_k| = n(n+1)$, 所以

$$\sum_{k=1}^{2n} \frac{\binom{T_k}{2}}{\binom{n+1}{2}} = \frac{\sum_{k=1}^{2n} |T_k|^2}{n(n+1)} - 1 \geq \frac{n}{2}-0.5$$

因为 $n$ 是偶数，$\geq n/2-0.5$ 等价于 $\geq n/2$。

题解：感性的想，多次随机 $(i,j)$ 时，总会随到 $|S_i \cap S_j| \ge n/2$。考察最坏情况：$E[|S_i \cap S_j|] = n/2$，且每次的交集要不是 $n/2-1$，要不是 $n$。那么前者和后者的比例是 $2:n$，即期望 $O(n)$ 次即可随机到答案，总时间复杂度为 $O(n^2)$。注意到本题还可以用 bitset 加速验证，即优化后的时间复杂度为 $O(\frac{n^2}{w})$。

卡内存版本的方格计数

题意：$n \times n$ 的矩阵，位置 $(i,j)$ 的权值是 $A_i \cdot B_j$。从 $(1,1)$ 走到 $(n,n)$，每次只能向右或者向下，问最大权值和能是多少，同时要求给出任意一组合法方案。$n \le 10000$，内存限制 2MB。

常规做法：设 $f_{i,j}$ 表示到位置 $(i,j)$ 的最大权值，$g_{i,j}$ 表示该位置是从上还是从左转移过来的。$f_{i,j}$ 显然可以用滚存做到空间 $O(n)$，但是 $g_{i,j}$ 不行，因为回溯方案的时候需要知道整个 $g$ 矩阵的信息。

优化一：bitset。由于 $g$ 中的信息只有 0 或 1，bitset 压缩后的空间是 $O(n^2/64)$，内存有所缓解但仍不能通过。

优化二：一种常被忽略的方法是利用时间换空间，即 $O(n^2)$ 计算每一步该怎么走，内存达标但时间 $O(n^3)$。

优化三：分块大法折衷！每 $S$ 行分一块，每次只计算一块的结果，时间 $O(n^3/S)$ 空间 $O(nS/64)$，还差一点！

优化四：分治大法！定义 $Solve(x_1,y_1,x_2,y_2)$ 表示对应矩阵的左上角走到右下角的最大权值和和方案。

1. 设 $m=(l+r)/2$，用 $O((x_2-x_1)(y_2-y_1))$ 的时间求出从第 $m$ 行去第 $m+1$ 行时所在的列。
2. 假设分割列是 $p$，递归 $Solve(x_1,y_1,mid,p)$ 和 $Solve(mid+1,p,x_2,y_2)$。

空间复杂度显然达标，时间复杂度是 $T(n)=O(n^2)+2T(n/2)=O(n^2)$，神奇！

动态 mex

题意：$n$ 个操作：1. 增加一个正整数；2. 删除一个已经添加过的正整数；3. 询问当前数字集合的 mex（最小的不在集合里的正整数）。给出一种 $O(n)$ 的做法，或证明不存在 $O(n)$ 的做法。

简化版：由于答案 $\le n$，增删数字的值域可简化成 $[1,n]$。我们还可以假设每个正整数最多只在集合中出现一次，因为我们可以用 $f_x$ 记录 $x$ 的出现次数，只有当 $f_x=1 \rightarrow0,0\rightarrow 1$ 变化时才需要更新答案。

结论和证明：不存在 $O(n)$ 的做法。构造一个“动态堆问题”：初始时堆里放了 $n$ 个数，分别是 $1,2,\dots,n$；$n$ 次操作，每次删除或增加一个数，或询问堆的最小值。显然对于任意一个“动态堆问题”，我们都能转化成对应的“简化版动态 mex 问题”（加删互换），即前者的复杂度下界一定是后者的复杂度下界。注意到 “动态堆问题” 涉及到的就是标准的堆操作，目前的共识是复杂度 $\Omega(n \log n)$，即证得“动态 mex 问题”不存在 $O(n)$ 的做法。

逆序对的另类求法

题意：给出 $n$ 个数，每个数的范围是 $[1,n]$，如何不用分治和数据结构求逆序对数量？

题解：给出一个基于二进制和桶排的做法：对于每一组逆序对 $(x,y)$，分别考虑 $a_x$ 和 $a_y$ 的二进制表示 $B_x,B_y$。因为 $a_x>a_y$，所以必然存在一个位置 $i$，使得 $B_{x,1 \sim i}>B_{y,1 \sim i}$——在位置 $i$ 处统计贡献。

整个算法分为 $O(\log V)$ 轮。每一轮执行以下操作：

1. 从 $1$ 到 $N$ 遍历，如果 $a_x$ 是奇数就 $cnt_{a_x}++$，如果 $a_x$ 是偶数就 $ans+=cnt_{a_x+1}$。
2. 每个数都对 $2$ 下取整。如果某个数变成 $0$ 了，下一轮将不再考虑。

显然总复杂度是 $O(n \log V+V)$。

边权为 1 的无向图最小环

题意：给出一张 $n$ 个点 $m$ 条边的无向图，每条边的长度都是 $1$。求图上长度不低于 $2$ 的最小环。

做法：熟知 Floyd 可以 $O(n^3)$ 求无向图或有向图的最小环，而本题其实存在 $O(n^2)$ 的做法。枚举最小环里的一个点 $s$ 跑 BFS，如果当前点 $x$ 的后继 $y$ 已经被遍历过，把 $f_x+f_y+1$ 更新答案并立即退出。对所有点都做一遍，取 min 即为最小环的大小。由于每个点最多被遍历一次，复杂度是 $O(n^2)$。

说明：设点 $s$ 所在的最小环环长是 $C_s$，最小环的环长是 $C_m$，如果不存在环则 $C=+\infty$。从 $s$ 开始 BFS 的结果只满足 $C_s \ge f_x+f_y+1\ge C_m$，$C_s=f_x+f_y+1$ 并不成立。例如，图 $1-2-3, 3-4-6, 3-5-6$ 中 $1$ 根本不在任何环里，上述做法还是会把 $f_4+f_5+1$ 更新答案。不过这一步并不会影响最小环的正确性，因为出现这种情况时一定存在环了，且当前值严格劣于最小环。

求k组出现了奇数次的数字

题意：已知 $N$ 个数中恰好有 $k$ 个不同的数字出现了奇数次。只能扫一遍，要求出这 $k$ 个数。$N$ 很大，$k \leq 10$，内存很小。据说题目来自 NOI 国家队集训。

题解：$k=1$ 是异或，$k=2$ 是维护 $\log N$ 个异或，下面讲解 $2 < k \le 10$ 的做法。

子问题：先从一个入手。对于一个数字集合 $S$，如何判断是否只有一个数字出现了奇数次？除了要求速度快、内存小，还要求能动态增加数字，以及快速合并两个集合。

基于概率的子问题解法：取一个模数 $P$（如 $998244353$）以及模域下的一个常数 $c$。

对于每一个进来的数 $x$，取一个映射 $y=xP+c$，维护 $y$ 的异或和 $xor_y$。如果只有一个数字出现了奇数次，必然有 $xor_y \mod P=c$；反之，我们可以认为不成立。同时维护 $x$ 的异或和可还原方案。多取几组 $(P_i,c_i)$ 后可以认为能稳定判断并还原，称这一套完整的机制为一个“判定机器”。

基于概率的原问题解法：维护 $m$ 个独立的判定机器（比如取 $m=20$），彼此独立。每次来了一个数字 $x$ 后，依次枚举判定机器，每个判定机器都有 $\frac{1}{2}$ 的概率插入这个数字。注意要保证相同的 $x$ 对于相同的判定机器“是否插入的行为”是一致的（如对 $x$ 施加哈希函数，用二进制位决定是否插入）。上述操作保证了：对于任何一个判定机器，总共出现了偶数次的数字一定插入了偶数次，总共出现了偶数次的数字（我们要求的数字）插入了偶数次还是奇数次的概率是均等的。$N$ 个数字插入完成后，枚举判定机器里所有 $2^m$ 个子集。对于一个子集 $S$，合并对应的判定机器，看看总集合里 是否只有一个数字 $t$ 出现了奇数次。如果是，他必然是这 $k$ 个答案中的一个。枚举完所有子集后，汇总去重即为答案。

准确率证明：上述算法求得的答案必然正确，但是有概率漏解。考虑一个行数为 $k$，列数为 $m$ 的01矩阵。$0$ 和 $1$ 表示这个答案 $t$ 在这个数字集里是否出现奇数次。如果能枚举到所有 $k$ 个答案，说明对于每一行，都存在至少一个列集合 $S$，满足列集合异或后是这一行的 one hot。进一步能推导出，这个矩阵满秩（在在异或空间下考虑问题）；反过来，如果该矩阵满秩，列向量就能组合出所有 $2^k$ 列向量，当然也能拼成 one hot。也就是说，能搜到所有解和矩阵满秩是充要的。问题转化成：$k \times m$ 的矩阵里每个元素出现 $0$ 和 $1$ 的概率均等，求其不满秩（出错）的概率。这个东西可以递推来求。固定 $k$，从小到大递推 $m$，我们有 $f_{k,0}=1,f_{k,i}=(1-f_{k,i-1})2^{i-1-k}$。回到题目 $k=10$， 取 $m=20$ 时正确率 $99.7\%$，$m=25$ 时正确率 $99.997\%$。

和至少为 K 的最短子数组

题意：给出一个可能有负数的整数数组和一个阈值 $k$，找一个长度尽量小的子串使得和 $\ge k$。Leetcode 862

题解：前缀和后就是找 $\min \limits_{sum_r-sum_{l}\ge k}(r-l)$。对于 $l_1<l_2$，如果有 $sum_{l_1} \le sum_{l_2}$，则 $l_2$ 一定优于 $l_1$（值更小长度也更小）。根据这个性质构建单调队列，查询 $r$ 时在单调队列中二分出最近的合法 $l$，复杂度 $O(N \log N)$。

线性做法：继续挖掘性质，如果 $sum_r-sum_l \ge k$，则该 $l$ 不会用于更大的 $r$。在上述单调队列的基础上，每当处理完当前 $r$ 后就弹队首，直到 $sum_r-sum_{head}<k$。最后一个被弹出的 $l$ 是当前 $r$ 的答案。

01 背包求方案

题意：$n$ 个物品，体积分别为 $a_i$，求一组体积凑到 $m$ 的方案。$\sum a_i,m \le 10^5$，内存限制 32M。From Claris。

题解：朴素的 01 背包+bitset 实现的复杂度是 $O(nm/w)$，空间上难以通过本题。为了节省内存，先用一个 bitset 求出最后的 $f$ 数组，暴力倒推回去，每次重新扫：空间虽然是 $O(m/w)$ 的，时间退化成了 $O(n^2m/w)$。

分块：将上述两个做法合并：按大小 $T$ 对序列分块，记忆化每块的前缀背包结果来加速倒推时的重新计算，那么空间复杂度 $O(nm/Tw)$，时间复杂度 $O(n^2m/Tw)$，折衷后的效果依然达不到我们的要求。

标准做法：上述做法只利用了背包可以线性塞入一个物品，没利用到背包还可以线性将总集合的体积任务分解成两个集合各自的任务。以 $O(\sqrt n)$ 大小对序列分块，同样记录前缀背包的结果。以块的粒度倒推，每次线性将目标 $m$ 拆解成 $m_1+m_2$ 的形式分解给当前块和前缀块。一个块内可以再暴力做一遍背包以具体判断每个物品是否使用。重复利用数组的话，我们只需要一组 $(m/w)\sqrt n$ 大小的 bitset 即可在时间复杂度 $O(nm/w)$ 求解成功。

01 背包在线更新

题意：维护一个可重数字集合 $S$。若干次操作，每次要不往集合里插入一个正整数 $x$，要不查询当前 $S$ 是否存在一个和为 $y$ 的子集。强制在线。保证 $x>0,y \le n=\sum x \le 10^6$。From Claris。

建模：很显然的背包模型，朴素的 01 背包+bitset 实现的复杂度是 $O(n^2/w)$，时空上都不足以通过本题。

$$f'=f~|~f<<v$$

考察 bitset 的更新公式：本质上我们只想知道 $f << v$ 相比于 $f$ 增加的位置（$0 \rightarrow 1$）。如果能 $O(size)$ 找到这些位置，总时间复杂度就是可观的 $O(n)$，因为每个位置最多被找一次。很遗憾没法直接找到，我们尝试将其拓展成异或，即 $f<<v$ 相比 $f$ 不同的位置（$0 \rightarrow 1$ 或 $0 \rightarrow 1$）。显然 $|P_{0 \rightarrow 1}|=|P_{1 \rightarrow 0}|$，所以如果我们能 $O(2size)$ 筛选出这些异或的位置再暴力检查，复杂度仍然是正确的。那么上述逻辑转化成了以下问题：

转化求解：实时维护一个 01 序列，每次需要快速定位 $[0,n-v]$ 和 $[v,n]$ 两个子串里所有数值不同的位置。使用经典的线段树维护哈希就能很方便地做到这一点，所以本题的时间复杂度不超过 $O(n \log n)$。