AT2300 [ARC068C] Snuke Line

题目描述

https://www.luogu.com.cn/problem/AT2300

简要题意：给定 $m$ 个区间 $[l_i,r_i]$，现在有 $n$ 个人，每个人都从 $0$ 出发，第 $i$ 个人每次只能走 $i$，即他经过的位置都是 $i$ 的倍数，求每个人经过的位置属于多少种区间

$n\le 3\times 10^5,m\le 10^5$

Solution

我们考虑对于一个人 $x$，他经过的位置属于区间 $[l_i,r_i]$ 当前仅当 $\lfloor\frac{l-1}{x}\rfloor<\lfloor\frac{r}{x}\rfloor$，我们考虑直接数论分块 $x$，每次比较两者的值做区间加即可

时间复杂度 $O(m\sqrt n)$

#include <iostream>
#define maxn 300010
using namespace std;

int n, m;
int d[maxn];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> m >> n;
    for (int i = 1; i <= m; ++i) {
        int x, y; cin >> x >> y; --x;
        for (int l = 1, r; l <= x; l = r + 1) {
            r = min(x / (x / l), y / (y / l));
            if (x / l < y / l) ++d[l], --d[r + 1];
        }
        ++d[x + 1]; --d[y + 1];
    }
    for (int i = 1; i <= n; ++i) {
        d[i] += d[i - 1];
        cout << d[i] << "\n";
    }
    return 0;
}