补题情况
| 题目 | 蒋贤蒙 | 王赵安 | 王智彪 |
|---|---|---|---|
| A | 2 | 0 | 0 |
| D | 0 | 0 | 0 |
| E | 2 | 0 | 0 |
| F | 0 | 0 | 0 |
| J | 0 | 0 | 0 |
| K | 0 | 0 | 0 |
题解
A. Bags of Candies
题意
多组数据。每组数据给定 $n\le 10^{11}$，定义两个数能匹配当且仅当两个数的最大公因数不唯一，求 $1\sim n$ 的最大匹配数。
打表法
设 $D(n)$ 表示大于 $\lfloor \frac n2\rfloor$ 的质数个数。首先证明答案为 $\lfloor\frac {n-D(n)-1}2\rfloor$。
首先 $1$ 和任意大于 $\lfloor \frac n2\rfloor$ 的质数显然都不能配对，所以这是答案上界。
对其他数，将它放入它的最大素因子所在的桶中。于是对每个素因子 $P$，桶中至少有 $P,2P$。如果桶中有偶数个数，直接两两配对。
否则将 $2P$ 放入 $2$ 的桶中，其他两两配对。易知最后至多只剩下一个数，证毕。
接下来考虑如何计算 $D(n)$，考虑分段打表，每个段大小为 $10^7$，统计该范围内的素数个数。
然后查询时预处理完整段的前缀和，处理最后一个不完整的段的答案即可。
关于查询区间 $[L,R]$ 答案，可以用埃氏筛 $O(\sqrt n)$ 预处理后 $O\left((r-l)\log\log(r-l)\right)$ 查询。
打表复杂度 $O(n\log\log n)$，每组数据复杂度 $O(10^7\log\log n)$，打表时间比较长而且打表数据需要压缩。
E. Contamination
题意
二维平面中给定 $n$ 个圆。接下来 $q$ 个询问，每次询问给定 $P(x,y),Q(x,y),y_1,y_2$，问 $P$ 是否可以移动到 $Q$。
移动过程中不能进入圆的范围且 $y$ 始终在 $[y_1,y_2]$。保证 $P,Q$ 一定不属于任意一个圆，且任意两圆都相离。
题解
不妨设 $P_x\le Q_x$。不难发现，$P$ 可以移动到 $Q$ 的充要条件为不存在一个圆 $(x,y,r)$ 满足 $P_x\le x\le Q_x$ 且 $y-r\le y_1,y+r\ge y_2$。
考虑扫描线维护答案，将所有询问按 $y$ 排序，对每个圆，在 $y=y_i-r_i$ 时加入贡献，$y=y_i+r_i$ 时删除贡献。
线段树维护 $X$ 轴区间上每个位置的有效的圆的 $y+r$ 的最大值。于是题目转化为单点修改、区间查询。
对每个叶子额外开一个多重集维护该位置的 $y+r$ 的最大值即可，时间复杂度 $O((n+q)\log n)$。
