【AtCoder Regular Contest 068 E】Snuke Line | Mrsrz's blog

树状数组。

题目大意：

数轴上有 $n$ 条线段，对 $i\in[1,m]$，求出有多少条线段覆盖到了 $i$ 的倍数位置。

题解：

由于长度大于等于 $d$ 的线段一定覆盖到了 $d$ 的倍数，而长度小于 $d$ 的线段最多覆盖到一个 $d$ 的倍数位置。

所以我们预处理出长度大于等于 $d$ 的线段条数，然后从小到大枚举 $i$ 以及 $i$ 的倍数。对每个位置求出小于 $i$ 的覆盖它的线段条数即可。可以使用树状数组维护。

时间复杂度 $O(m\log^2 m)$。

Code：

#include<cstdio>
#include<vector>
const int N=3e5+5;
int n,m,L[N],R[N],B[N],c[N],s;
std::vector<int>X[N],Y[N];
inline void add(int i,int x){for(;i<=m;i+=i&-i)B[i]+=x;}
inline int ask(int i){int x=0;for(;i;i&=i-1)x+=B[i];return x;}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        scanf("%d%d",L+i,R+i);
        int l=R[i]-L[i]+1;
        ++c[l],X[l].push_back(L[i]),Y[l].push_back(R[i]+1);
    }
    for(int i=m;i;--i)c[i]+=c[i+1];
    for(int i=1;i<=m;++i){
        s=c[i];
        for(int j=i;j<=m;j+=i)s+=ask(j);
        printf("%d\n",s);
        for(int x:X[i])add(x,1);
        for(int x:Y[i])add(x,-1);
    }
    return 0;
}