ARC068C Snuke Line

LuoGu: AT2300 [ARC068C] Snuke Line

AtCoder: E - Snuke Line

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

• 在 $1\dots l-1$ 区间的列车，可以用数论分块。对于一段区间的每个数 $x$ ，如果每个 $\frac{l-1}{x}$ 和 $\frac{r}{x}$ 都相等，则这段区间的答案都加 $1$ ，可以用差分维护。
• 对于 $d>r$ 的区间，一定不会有答案。
• 在 $l\dots 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;
}