题意：

有n个区间，询问对于$1\leq i\leq m$的每个i，有多少个区间至少包含一个i的倍数？

$1\leq N\leq 3\times 10^5$

$1\leq M\leq 10^5$

题解：

开始就想到了调和级数的复杂度，但是一直没想到反着统计。。。

正着统计区间是否包含$i$的倍数很麻烦，不妨反过来统计是否不包含，那么不包含的情况肯定是区间卡在两个$i$的倍数之间或者在$\lfloor\frac{m}{i}\rfloor\times i$和$M$之间，用调和级数的时间复杂度可以把所有倍数搞出来。那么可以将询问离线，按照$i$的倍数分段，然后用树状数组维护即可。

调和级数一个$log$，树状数组一个$log$，所以最后的时间复杂度是$O(mlogmlogn)$

貌似有很多dalao用不同姿势的分块碾了过去QAQ

代码：

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<vector>

 #include<cmath>

 #define lb(x) (x&-x)

 using namespace std;

 struct task{

     int x,id;

 }a[];

 int n,m,l,r,tot=,ans[],t[];

 vector<int>g1[],g2[];

 void add(int x,int v){

     for(;x;x-=lb(x)){

         t[x]+=v;

     }

 }

 int query(int x){

     int ret=;

     for(;x<=m;x+=lb(x)){

         ret+=t[x];

     }

     return ret;

 }

 int main(){

     scanf("%d%d",&n,&m);

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

         scanf("%d%d",&l,&r);

         g1[r].push_back(l);

     }

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

         ans[i]=n;

         for(int j=;j<=m/i;j++){

             a[++tot].x=i*(j-);

             a[tot].id=i;

             g2[i*j].push_back(tot);

         }

         a[++tot].x=(m/i)*i;

         a[tot].id=i;

         g2[m+].push_back(tot);

     }

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

         for(int j=,jj=g2[i].size();j<jj;j++){

             ans[a[g2[i][j]].id]-=query(a[g2[i][j]].x+);

         }

         for(int j=,jj=g1[i].size();j<jj;j++){

             add(g1[i][j],);

         }

     }

     for(int i=;i<=m;i++)printf("%d\n",ans[i]);

     return ;

 }

巴特西

[arc086e]snuke line

题意：

题解：

代码：

最新文章

热门文章