ARC068C Snuke Line

考虑每一个商品对列车 $d$ 的贡献。对于一个商品在 $l…r$ 区间售卖，如果一个列车可以经过，则存在 $k$ ，使得：
$$
\begin {aligned}
&l \le kd \le r\\
\Longrightarrow & \frac l d \le k \le \frac r d\\
\Longrightarrow & \frac {l - 1} d < k \le \frac r d\\
\end {aligned}
$$
即
$$
\frac {l - 1} d < \frac r d
$$

在 $1…l - 1$ 区间的列车，可以用数论分块。对于一段区间的每个数 $x$ ，如果每个 $\frac {l - 1} x$ 和 $\frac r x$ 都相等，则这段区间的答案都加 $1$ ，可以用差分维护。
对于 $d > r$ 的区间，一定不会有答案。
在 $l…r$ 的区间一定有答案，直接在差分数组上加即可。

查看代码

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int n, m, c[N];
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1, x, y; i <= n; i++)
    {
        scanf("%d%d", &x, &y);
        c[x]++;
        c[y + 1]--;
        x--;
        for (int l = 1, r; l <= x; l = r + 1)
        {
            r = min(x / (x / l), y / (y / l));
            if (x / l < y / l)
            {
                c[l]++;
                c[r + 1]--;
            }
        }
    }
    for (int i = 1, s = c[1]; i <= m; i++, s += c[i])
        printf("%d\n", s);
    return 0;
}