ARC068E Snuke Line

原题链接

有一趟列车有 $M + 1$ 个车站，从 $0$ 到 $M$ 编号。有 $N$ 种商品，第 $i$ 种只在编号 $[l_{i}, r_{i}]$ 的车站出售。一辆列车有一个预设好的系数 $d$ ，从 $0$ 出发，只会在 $d$ 的倍数车站停车。对于 $d$ 从 $1$ 到 $M$ 的列车，求最多能买到多少种商品。

$1 \leq N \leq 3 \times 10^{5}; 1 \leq M \leq 10^{5}; 1 \leq l_{i} \leq r_{i} \leq M$ 。

题解

我们考虑对于每个 $d$ ，如果区间 $[l_{i}, r_{i}]$ 有 $r_{i} - l_{i} + 1 \geq d$ ，那么显然它一定会被覆盖，我们直接统计答案。

我们考虑 $r_{i} - l_{i} + 1 < d$ 的情况，显然它只会被覆盖一次，所以我们只要求这些区间与这些点的交点个数即可。

于是我们由长度从小到大枚举区间，放入线段树中。对于每个 $d$ 枚举点。由于点的总数是 $T (n) = \sum_{i = 1}^{n} \frac{n}{i} = O (n \ln n)$ ，所以复杂度为 $O (n \log^{2} n)$ 。

代码

cpp

#include <cstdio>
#include <iostream>
#include <algorithm>

using namespace std;

const int maxn = 300005;

int n, m;

#define lowbit(x) (x & (-x))

struct Tree
{
    int no[maxn];

    inline void add(int pla, int x)
    {
        for (; pla <= m; pla += lowbit(pla))
            no[pla] += x;
    }

    inline void add_qj(int l, int r)
    {
        add(l, 1);
        if (r < m)
            add(r + 1, -1);
    }

    inline int query(int pla)
    {
        int ans = 0;
        for (; pla; pla -= lowbit(pla))
            ans += no[pla];
        return ans;
    }
} tr;

struct QJ
{
    int l, r;
    inline int len() { return r - l + 1; }
    friend bool operator < (QJ a, QJ b)
    { return a.r - a.l < b.r - b.l; }
} qj[maxn];

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i)
        scanf("%d%d", &qj[i].l, &qj[i].r);
    sort(qj + 1, qj + n + 1);
    int now = 1;
    for (int i = 1; i <= m; ++i)
    {
        while (now <= n && qj[now].len() < i)
        {
            tr.add_qj(qj[now].l, qj[now].r);
            now++;
        }
        int ans = n - now + 1;
        for (int j = 0; j <= m; j += i)
            ans += tr.query(j);
        printf("%d\n", ans);
    }
    return 0;
}

题解

代码

Cite this post