ARC068E Snuke Line

#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;
}