arc068e

题意：m个区间，对1到n的i分别求有多少个区间中出现了i的倍数。

对于数i，长度大于等于的区间i一定包含i的倍数，长度小于i的区间最多包含一个i的倍数，从小到大枚举i，每次把长度小于i的区间从答案中减掉，插入树状数组中。枚举i的倍数，对于i的每个倍数在树状数组中查询。
写了个sb线段树。。。

#include <bits/stdc++.h>
using namespace std;
#define ls l,mid,now<<1
#define rs mid+1,r,now<<1|1
const int N=310000,M=110000;
int n,m,cnt;
struct node
{
    int l,r;
    friend bool operator < (const node &r1,const node &r2)
    {return r1.r<r2.r;}
}a[N];
vector<int>vec[M];
int b[M*20],pos[M],ed[M],beg[M],nv[M*20];
int val[M*20],bj[M*80],ans[M];
void pushdown(int now)
{
    bj[now<<1]+=bj[now];
    bj[now<<1|1]+=bj[now];
    bj[now]=0;
}
void modify(int l,int r,int now,int pos,int v)
{
    if(l==r)
    {
        val[l]+=bj[now]*nv[l];
        bj[now]=0;nv[l]=v;
        return;
    }
    int mid=(l+r)>>1;
    pushdown(now);
    if(mid>=pos)modify(ls,pos,v);
    else modify(rs,pos,v);
}
void insert(int l,int r,int now,int lq,int rq)
{
    if(lq<=l&&r<=rq)
        {bj[now]++;return;}
    int mid=(l+r)>>1;
    if(mid>=lq)insert(ls,lq,rq);
    if(mid<rq) insert(rs,lq,rq);
}
void down(int l,int r,int now)
{
    if(l==r)
    {
        val[l]+=bj[now]*nv[l];
        return;
    }
    int mid=(l+r)>>1;
    pushdown(now);
    down(ls);down(rs);
}
int main()
{
    //freopen("tt.in","r",stdin);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&a[i].l,&a[i].r);
    sort(a+1,a+1+n);
    for(int i=1;i<=m;i++)
        for(int j=i;j<=m;j+=i)
            vec[j].push_back(i);
    for(int i=1;i<=m;i++)
    {
        beg[i]=cnt+1;
        for(int j=0;j<vec[i].size();j++)
            b[++cnt]=vec[i][j];
        ed[i]=cnt;
    }
    for(int i=1,now=1,t=0;i<=m;i++)
    {
        while(t<ed[i])
        {
            t++;
            if(pos[b[t]])
                modify(1,cnt,1,pos[b[t]],0);
            modify(1,cnt,1,t,1);
            pos[b[t]]=t;
        }
        while(now<=n&&a[now].r==i)
        {
            insert(1,cnt,1,beg[a[now].l],ed[a[now].r]);
            now++;  
        }
    }
    down(1,cnt,1);
    for(int i=1;i<=cnt;i++)
        ans[b[i]]+=val[i];
    for(int i=1;i<=m;i++)
        printf("%d\n",ans[i]);
    return 0;
}