AtCoder

Luogu

分析

先考虑对于每个 $d\in[1,m]$ 如何单独算答案。

可以发现,对于 $r_i-l_i+1\geq d$ 的那些商品,它们一定能被买到;对于 $r_i-l_i+1<d$ 的那些商品,它们只能够被买到至多一次。

我们可以找到所有 $r_i-l_i+1<d$ 的商品,将 $[l_i,r_i]$ 加上 $1$,然后再算所有 $d$ 的倍数的位置上的数的和,就能得到能买到的 $r_i-l_i+1<d$ 的商品的数量了;再加上 $r_i-l_i+1\geq d$ 的商品即可得到答案。

回到这道题中。我们把所有商品按 $r_i-l_i+1$ 从小到大排序,然后用一个指针维护 $r_i-l_i+1<d$ 的位置,每次移动指针并进行修改,然后统计答案。具体实现上可以用树状数组进行维护。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>  
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=300000+10,M=100000+10;

int n,m;
struct node { int l,r; } a[N];
bool operator <(node a,node b) { return a.r-a.l<b.r-b.l; }

int c[M];
inline void add(int x,int y) { for (;x<=m;x+=x&-x) c[x]+=y; }
inline int sum(int x) { int s=0; for (;x;x-=x&-x) s+=c[x]; return s; }

int main() {
    n=read(),m=read();
    for (re int i=1;i<=n;++i) a[i].l=read(),a[i].r=read();
    sort(a+1,a+n+1);
    for (re int i=1,p=0;i<=m;++i) {
        while (p<n&&a[p+1].r-a[p+1].l+1<=i)
            ++p,add(a[p].l,1),add(a[p].r+1,-1);
        int ans=0;
        for (re int j=i;j<=m;j+=i) ans+=sum(j);
        printf("%d\n",ans+n-p);
    }
    return 0;
}
最后修改:2020 年 01 月 14 日 03 : 31 PM