传送门

直接把每个$d$值可能经过的所有点存起来,再根据每个点的下一个点的位置,可以把每个商品转换成平面上一个矩形内所有点+1,直接离线+树状数组就行了。因为总共有$O(n\log n)$个点,再加上数据结构总体复杂度就是$O(n\log^2n)$了。

无压力1A。(也就只有这些水题能1A了)

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 2000010
using namespace std;

int read(){
    char c;
    while((c=getchar())<'0' || c>'9');
    int res=c-'0';
    while((c=getchar())>='0' && c<='9') res=res*10+c-'0';
    return res;
}

int n,m,numq;
int p[MAXN][2];
int ans[MAXN];

namespace Fenwick{
    int c[MAXN];

    void add(int x,int v){
        x++;
        while(x<=n+1){
            c[x]+=v;
            x+=x&(-x);
        }
    }

    int sum(int x){
        x++;
        int res=0;
        while(x){
            res+=c[x];
            x-=x&(-x);
        }
        return res;
    }
}

struct Event{
    int x1,x2,y,id;
}q[MAXN];

bool cmp(Event x,Event y){
    if(x.y==y.y) return x.id<y.id;
    return x.y<y.y;
}

int main(){
#ifdef DEBUG
    freopen("E.in","r",stdin);
#endif
    m=read(); n=read();
    for(int i=1;i<=m;i++){
        p[i][0]=read(); p[i][1]=read();
        q[++numq]=(Event){p[i][0],p[i][1],p[i][1]+1,0};
    }
    for(int i=1;i<=n;i++)
        for(int j=i;j<=n;j+=i)
            q[++numq]=(Event){j,j,j+i,i};
    sort(q+1,q+numq+1,cmp);
    for(int i=1;i<=numq;i++)
        if(q[i].id) ans[q[i].id]+=Fenwick::sum(q[i].x1);
        else Fenwick::add(q[i].x1,1),Fenwick::add(q[i].x2+1,-1);
    for(int i=1;i<=n;i++) printf("%d\n",ans[i]);
    return 0;
}