[arc068e] Snuke Line 树状数组

Description

​ 有一趟列车有$ M+1M+1$ 个车站，从 $00 $到 (MM) 编号。有 NN 种商品，第 ii 种只在编号 $[li,ri][li,ri] $的车站出售。一辆列车有一个预设好的系数 dd，从 00 出发，只会在 dd 的倍数车站停车。对于 dd 从 11 到 MM 的列车，求最多能买到多少种商品。

Input

​ 第一行两个整数 NN 和 MM。

​ 接下来 NN 行每行两个整数 li,rili,ri。

Output

​ MM 个整数，第 ii 行表示列车系数为 ii 时最多能买到的商品种类数。

Sample Input

Sample #1
3 3
1 2
2 3
3 3

Sample #2
7 9
1 7
5 9
5 7
5 9
1 1
6 8
3 4

Sample Output

Sample #1
3
2
2

Sample #2
7
6
6
5
4
5
5
3
2

HINT

1≤N≤3×10^51≤N≤3×105

1≤M≤10^51≤M≤105

1≤li≤ri≤M1≤li≤ri≤M

Sol

我们发现，如果一个商品的长度大于等于停站间隔，那么一定能够选上，我们只需要考虑小于的即可。我们按照停站间隔从小到大枚举，用树状数组差分，然后调和级数查询，大于的直接维护cnt。

Code

#include <bits/stdc++.h>
using namespace std;
int n,m,s[500005],l[500005],r[500005],ans;vector<int>v[500005];
void add(int x,int v){for(;x<=m;x+=x&-x) s[x]+=v;}
int que(int x){int r=0;for(;x;x-=x&-x) r+=s[x];return r;}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d%d",&l[i],&r[i]),v[r[i]-l[i]+1].push_back(i);
    for(int i=1;i<=m;i++,ans=0)
    {
        for(int j=0;j<v[i].size();j++) add(l[v[i][j]],1),add(r[v[i][j]]+1,-1);
        for(int j=i;j<=m;j+=i) ans+=que(j);
        n-=v[i].size();printf("%d
",ans+n);
    }
}