arc068 E: Snuke Line

首先要知道 (m/1 + m/2 + ... + m/m) 约为 mlogm

还有一个比较明显的结论，如果一个纪念品区间长度大于d，那么如果列车的停车间隔小于等于d，则这个纪念品一定能被买到

然后把区间按长度排序

枚举d，边枚举边加那些长度小于d的区间到线段树当中，这样可以保证一个纪念品不会被加2次

最后输出答案即可

#include <iostream>

#include <algorithm>

using namespace std;

const int Maxn = *;

namespace seqtree

{

    struct Tree

    {

        Tree *ch[];

        long long _v, label;

        int Num, _l, _r, mid;

        Tree() { _v = label = ; Num = ; }

        void update();

        void maintain();

    }Node[Maxn], *null, *Root;

    int tot = , _k, _L, _R;

    long long v;

    void Tree::update()

    {

        if(!label) return;

        _v += Num*label;

        if(Num != ) ch[]->label += label, ch[]->label += label;

        label = ;

    }

    void Tree::maintain()

    {

        ch[]->update(); ch[]->update();

          _v = ch[]->_v + ch[]->_v;

    }

    void protect()

    {

       null = new Tree();

       null->ch[] = null->ch[] = null; null->Num = ;

    }

    void insert(Tree *&o, int l, int r)

    {

        int mid = (l+r)/;

        if(o == null)

        {

             o = &Node[tot++];

             o->ch[] = o->ch[] = null;

             o->_l = l; o->_r = r; o->mid = (l+r)/;

        }

        if(l == r) { o->_v = v; return; }

        if(_k <= mid) insert(o->ch[], l, mid);

        else insert(o->ch[], mid+, r);

        o->maintain(); o->Num = o->ch[]->Num + o->ch[]->Num;

    }

    Tree* Build(int n, long long *a)

    {

          protect(); Root = null;

           for(int i = ; i <= n; i++) _k = i, v = a[i], insert(Root, , n);

           return Root;

    }

    long long query(Tree *o)

    {

        long long ans = ;

        o->update();

        if(_L <= o->_l && o->_r <= _R) return o->_v;

        if(_L <= o->mid) ans += query(o->ch[]);

        if(_R > o->mid) ans += query(o->ch[]);

        return ans;

    }

    long long Query(int L, int R) { _L = L; _R = R; return query(Root); }

    void change(Tree *o)

    {

      o->update();

      if(_L <= o->_l && o->_r <= _R) { o->label += v; o->update(); return; }

      if(_L <= o->mid) change(o->ch[]);   if(_R > o->mid) change(o->ch[]);

      o->maintain();

    }

    void Change(int L, int R, int V) { _L = L; _R = R; v = V; change(Root); }

};

using namespace seqtree;

struct Data

{

    int l, r, v;

    bool operator < (const Data &B) const

    { return v < B.v; }

}A[Maxn];

int n, m, l, r;

long long a[Maxn], ANS[Maxn];

int main()

{

    cin.sync_with_stdio(false);

    cin>>n>>m;

    Build(m+, a);

    for(int i = ; i < n; i++)

    {

        cin>>A[i].l>>A[i].r;

        A[i].v = A[i].r - A[i].l + ;

    }

    sort(A, A+n);

    int k = ;

    for(int i = ; i <= m; i++)

    {

        for(; A[k].v < i && k < n; k++)  Change(A[k].l, A[k].r, );

        int ans = n - k;

        for(int j = i; j <= m; j += i) ans += Query(j, j);

        cout<<ans<<endl;

    }

}