[AT2300] Snuke Line

题目大意

有一趟列车有 M+1 个车站，从 0 到 M 编号。有 N 种商品，第 i 种只在编号 [li,ri] 的车站出售。一辆列车有一个预设好的系数 d，从 0 出发，只会在 d 的倍数车站停车。对于 d 从 1 到 M 的列车，求最多能买到多少种商品。

链接

洛谷

解析

首先对于每个d，如果一个商品出现区间的长度大于等于d，那么这个商品一定能被买到。如果一个商品的出现区间小于d，那么这个商品最多只会在一个停留点出现一次。

所以我们可以把问题转化为一个区间修改单点查询的问题。对于区间不小于d的商品，我们直接加进答案，否则用树状数组在对应区间修改。然后枚举d的倍数，单点查询统计答案。具体的，首先我们把所有商品按区间长度从小到大排序，然后用一个指针记录当前最后一个区间长度小于d的商品的位置。枚举d时，每次后移指针，每移动到一个新商品就区间修改。答案就是枚举d的倍数查询结果的和加上没有加入树状数组的商品个数。

树状数组区间修改+单点查询可以借助差分实现。

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#define N 300002
using namespace std;
struct shop{
    int l,r;
}a[N];
int n,m,i,j=1,d,c[N];
int read()
{
    char c=getchar();
    int w=0;
    while(c<'0'||c>'9') c=getchar();
    while(c<='9'&&c>='0'){
        w=w*10+c-'0';
        c=getchar();
    }
    return w;
}
int my_comp(const shop &x,const shop &y)
{
    return x.r-x.l<y.r-y.l;
}
int lowbit(int x)
{
    return x&(-x);
}
int ask(int x)
{
    int ans=0;
    for(int i=x;i>=1;i-=lowbit(i)) ans+=c[i];
    return ans;
}
void add(int x,int y)
{
    for(int i=x;i<=m+1;i+=lowbit(i)) c[i]+=y;
}
int main()
{
    n=read();m=read();
    for(i=1;i<=n;i++) a[i].l=read()+1,a[i].r=read()+1;
    sort(a+1,a+n+1,my_comp);
    for(d=1;d<=m;d++){
        while(j<=n&&a[j].r-a[j].l<d){
            add(a[j].l,1);
            add(a[j].r+1,-1);
            j++;
        }
        int ans=n-j+1;
        for(i=1;i<=m+1;i+=d) ans+=ask(i);
        printf("%d\n",ans);
    }
}

[AT2300] Snuke Line

原文：https://www.cnblogs.com/LSlzf/p/12234991.html