自闭并坚持着
#持续更新#
# 小引
马上（周六）就要 CSP 了，继续做题找灵感。毕竟是最后一次了，每一场都当成退役前的最后一次比赛打吧。
# T1 - Snuke Line
> Linked AtCoder ARC068-E
点击展开/折叠题面
在 $0\sim m$ 的数轴上，给出 $n$ 段区间 $[l_i,r_i]$。对每个 $i\in[1,m]$，求出多少个区间中存在 $i$ 的倍数。
$m\le10^5,n\le3\times10^5$
- $O(n\sqrt m)$（TLE）
对于 “$[l,r]$ 中是否有 $i$ 的倍数” 这个条件可以这样处理：计算 $\le r$ 的最后一个 $i$ 的倍数 $\lfloor\frac ri\rfloor i$，判断它在不在 $[l,r]$ 内，即判断是否有 $\lfloor\frac ri\rfloor i\ge l$。
看到有下取整，则可以考虑数论分块，对于所有 $d=\lfloor\frac ri\rfloor$ 相同的 $i$，需要满足 $i\ge \lceil\frac ld\rceil$，则这些 $i$ 构成一个区间，可以差分统计答案。
复杂度 $O(n\sqrt m)$。
- $O(n\log^2 n)$（AC）
仍然是对于条件的处理。正难则反，对于 $i$，计算有多少个区间中没有 $i$ 的倍数，则这样的区间一定在两个 $i$ 的倍数之间（包括 $0$）。
于是我们相当于询问有多少个区间在 $(ki,ki+i)$ 之间，根据调和级数，询问的个数是 $O(n\log n)$ 的。
将这些询问离线，在数轴上扫描线。当扫描到位置 $p$ 时，将右端点为 $p-1$ 的区间加入数轴（保证了区间右端点在询问右端点左边）；然后回答右端点在 $p$ 的询问，即询问的左端点右边有多少个区间。
只需要单点修改查区间和，于是可以树状数组。
THE END
Thanks for reading!
> Linked 请笃信一个梦-网易云