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