目录
错题集 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)$。
6、Minimum Difference
题意
给定 $n$ 个位置，每个位置一个照明范围为 $p_i$ 的灯，如果该灯朝左，则照明区域为 $[i-p_i,i-1]$，如果该灯朝右，则照明区域为 $[i+1,i+p_i]$。
判定是否可以给每个灯一个朝向，使得 $[1,n]$ 区域全被照明，同时输出合法方案。
题解
设 $\text{dp}(i)$ 表示前 $i$ 个灯的最大照明前缀。
设 $\text{pre}(i)$ 如果为 $0$ 则表示第 $i$ 个灯没有约束，如果不为 $0$ 则表示第 $i$ 个灯强制朝左且第 $[\text{pre}(i)+1,i-1]$ 灯贪心朝右。
如果第 $i$ 个灯强制朝左，则考虑与之前的照明前缀拼接，于是需要找到 $j$ 满足 $\text{dp}(j)+1\ge i-p_i$。如果存在 $j$，则 $\text{dp}(i)$ 至少为 $i-1$。
然后 $j+1\sim i-1$ 的所有灯可以贪心考虑全部朝右，于是可以选取 $\max_{j+1\le k\le i-1} (i+p_i)$ 更新 $\text{dp}(i)$，可以 $\text{ST}$ 表维护。
另外如果 $\text{pre}(j)=0$，即 $j$ 没有强制向左的约束，还可以用 $j+p_j$ 更新 $\text{dp}(i)$。
不难发现满足条件的 $j$ 越小 $\text{dp}(i)$ 越大，于是权值线段树维护满足条件的最小下标即可。
如果第 $i$ 个灯朝右，首先 $\text{dp}(i)$ 至少为 $\text{dp}(i-1)$。如果 $\text{dp}(i-1)\ge i$，则 $\text{dp}(i)\gets i+p_i$。
最后，如果强制朝左的收益大于朝右的收益，则强制朝左且 $\text{pre}(i)=j$，否则贪心朝右且 $\text{pre}(i)=0$。
输出方案所有灯贪心朝右，遇到 $\text{pre}(pos)\neq 0$ 则把该灯改成朝左且跳转到 $\text{pre}(pos)$ 即可。
7、Make Them Similar
题意
给定一个长度为 $n$ 的序列 $a_1,a_2\cdots a_n$，要求找到 $x$ 使得 $a_1\oplus x,a_2\oplus x\cdots a_n\oplus x$ 中的二进制表示的 $1$ 一样多。
其中 $n\le 100,a_i\lt 2^{30}$。
题解
暴力枚举 $x$ 的低 $15$ 位和高 $15$ 位。假设当前枚举低 $15$ 位，且当前枚举的数为 $v$，记 $b_i$ 为 $a_i\oplus v$ 的二进制表示中的 $1$ 的个数。
将 $b_2-b_1,b_3-b_1\cdots b_n-b_1$ 所代表的序列插入字典树。然后枚举高位时查看有无刚好可以构成相反数的序列即可。
时间复杂度 $O(n\sqrt v)$。
