AT2300 Snuke Line

30 October 2019 | duanyll | Tags: OI 题解 树状数组

题意

有一趟列车有 $M+1$ 个车站, 从 0 到 M 编号. 有 N 种商品, 第 i 种只在编号 $[l_i,r_i]$ 的车站出售. 一辆列车有一个预设好的系数 d, 从 0 出发, 只会在 d 的倍数车站停车. 对于 d 从 1 到 M 的列车, 求最多能买到多少种商品. $N \leq 3 \times 10^5, M \leq 10^5$

分析

对于每一种商品, 假设他的覆盖的区间长度为 $l$, 那么如果 $d \leq l$, 则这种商品一定能买到; 否则最多只能在一个点被买到. 那么对于每一个 $d$, $d > l$ 的情况直接将区间按长度排序后计数; 将所有 $l \leq d$ 的区间的答案加一, 总答案就是 $d, 2d, 3d, \cdots$ 这些位置上的答案之和 (由于需要用树状数组统计的区间最多只会被一个点查询, 所以能做到不重不漏).

复杂度分析: 由于 $n + \cfrac{n}{2} +\cfrac{n}{3} +\cdots=n\log n$, 树状数组的复杂度是 $\log n$, 所以总复杂度是 $n \log^2n$

代码

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

const int MAXN = 3e5 + 10;
const int MAXM = 3e5 + 10;

template <typename value_t>
class fenwick {
   public:
    fenwick(int n) {
        memset(c, 0, sizeof c);
        this->n = n;
    }

    void add(int i, value_t x) {
        while (i <= n) {
            c[i] += x;
            i += Lowbit(i);
        }
    }

    value_t sum(int x) {
        value_t sum = 0;
        while (x > 0) {
            sum += c[x];
            x -= Lowbit(x);
        }
        return sum;
    }

    value_t sum(int x1, int x2) { return sum(x2) - sum(x1 - 1); }

   private:
    value_t c[MAXN];
    int n;

    inline int Lowbit(int x) { return x & (-x); }
};

struct interval {
    int l, r;
} a[MAXM];
struct comp {
    bool operator()(const interval& a, const interval& b) {
        return a.r - a.l < b.r - b.l;
    }
};

#include <cctype>
#include <cstdio>

inline int read() {
    int X = 0, w = 0;
    char ch = 0;
    while (!isdigit(ch))
    {
        w |= ch == '-';
        ch = getchar();
    }
    while (isdigit(ch)) {
        X = (X << 3) + (X << 1) + (ch ^ 48);
        ch = getchar();
    }
    return w ? -X : X;
}

int main() {
    int n = read();
    int m = read();
    for (int i = 1; i <= n; i++) {
        a[i].l = read();
        a[i].r = read();
    }  
    sort(a + 1, a + n + 1, comp());
    fenwick<int>* tree = new fenwick<int>(m);
    int cur = 1;
    for (int d = 1; d <= m; d++) {
        while (cur <= n && a[cur].r - a[cur].l + 1 < d) {
            tree->add(a[cur].l, 1);
            tree->add(a[cur].r + 1, -1);
            cur++;
        }
        int ans = n - cur + 1;
        for (int i = d; i <= m; i += d) {
            ans += tree->sum(i);
        }
        cout << ans << endl;
    }
}