目录
错题集 4
1、小V的序列
题意
给定一个长度为 $n$ 的序列，保证序列中每个数取值随机。
接下来给定 $m$ 个询问，每次给定一个数 $b$，问序列中是否存在数与 $b$ 异或后二进制表示中 $1$ 的个数不超过 $3$。
题解
考虑将 $b$ 的二进制表示分成四部分，每部分表示一个长度为 $16$ 二进制数。
则如果要与 $b$ 异或后二进制表示中 $1$ 的个数不超过 $3$，则至少四部分要有一个部分与 $b$ 相同。
考虑将序列中的每个数分成四个，每个数投入对应位置二进制数的桶中，然后暴力查询，时间复杂度 $O\left(4\cfrac {nm}{2^{16}}\log v\right)$。
2、Sasha and Array
题意
给定一个长度为 $n$ 的序列 $A$，接下来两种操作，操作 $1$ 为区间加，操作 $2$ 为区间斐波那契和查询。
其中，定义 $f(1)=f(2)=1,f(n)=f(n-1)+f(n-2)$，$[l,r]$ 区间斐波那契和为 $\sum_{i=l}^r f(a_i)$
题解
对每个结点，维护区间矩阵和 $\begin{pmatrix}a_n \\a_{n+1}\\ \end{pmatrix}$ 以及 $2\times 2$ 的区间懒标记。
于是区间加 $v$ 转化为对区间 $[l,r]$ 的每个矩阵乘上 $\begin{pmatrix}0 & 1 \\ 1 & 1\\ \end{pmatrix}^v$。时间复杂度 $O(m\log n\log v)$。
3、Count The Rectangles
题意
给定若干水平线和竖直线，问可以构成多少矩形(保证水平线之间两两不相交，竖直线之间两两不相交)
题解
考虑扫描线，枚举每一条水平线，然后考虑与该水平线相交的竖直线和纵坐标大于该线的水平线。
扫描一遍 $y$ 轴，用树状树状维护此时与扫描线相交的竖直线的 $x$ 坐标。然后扫描到竖直线上端点则删去该 $x$ 坐标贡献。
如果扫描到水平线则查询该水平线与当前枚举的水平线的 $x$ 轴公共区间上的竖直线个数 $t$，于是答案增加 $\frac {t(t-1)}2$。
注意到对 $y$ 坐标相同的对象，应该先处理水平线然后处理竖直线。时间复杂度 $O(n^2\log v)$。
4、Median Sum
题意
给定 $n$ 个数，定义集合的权值为该集合中所有数的和。求这 $n$ 个数的集合的所有子集的权值构成的集合中的中位数。注意这里所有集合指可重集。
题解
设所有数的和为 $S$，一个子集 $s_1$ 的权值为 $w$，则一定有一个该子集的补集 $s_2$ 的权值 $S-w$ 与之对应。
于是中位数一定是不小于 $\frac S2$ 的第一个数。用 $\text{vis}$ 表示子集的可能值，对新加入的数 $a$，有 $vis_{k+a}=vis_{k+a}\text{ | }vis_a$。
考虑 $\text{bitset}$ 暴力位压一下，时间复杂度 $O\left(\frac {nS}{w}\right)=O\left(\frac {n^2v}{w}\right)$。
5、GCD or MIN
题意
给定 $n$ 个数，每次可以任选两个数进行 $\text{gcd}$ 或 $\min$ 操作得到一个新数再删去原来两个数。不断进行操作直到只剩下一个数。
问剩下的数一共有多少种可能的取值。
题解
首先不难发现剩下的数一定不大于 $\min (a)$。再通过观察不难发现答案等于所有不超过 $\min (a)$ 的仅通过 $\text{gcd}$ 操作可以得到的数。
首先 $\min (a)$ 一定可以得到，下面仅考虑小于 $\min (a)$ 的数 $v$。
记 $a$ 中所有满足 $v\mid a_i$ 的数为 $b_1,b_2\cdots b_k$。不难发现 $v$ 可以得到当且仅当 $\text{gcd}(b_1,b_2\cdots b_k)=v$。
于是可以遍历 $a_i$。对每个 $a_i$，遍历他们的所有因子 $d$，同时更新 $g(d)$。($d$ 从 $1$ 开始)
如果 $g(d)$ 不存在则将 $g(d)$ 设为 $a_i$，否则将 $g(d)$ 设为 $\text{gcd}(g(d),a_i)$。
最后答案为 $1+$ 所有满足 $g(d)==d$ 的 $d$ 的个数。时间复杂度 $O(n\sqrt v\log v)$。
