Atcoder【arc068E】Snuke Line

本文主要是介绍Atcoder【arc068E】Snuke Line，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

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

---

Input

    第一行两个整数 N 和 M。接下来 N 行每行两个整数 li,ri。

---

Output

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

---

Solution

首先是爆艹做法。
直接枚举d,2d,3d…
可以看到因为是调和级数所以时间复杂度<O(nlogn)
然后随便搞就是了，也可以从反面考虑，用全部情况减去不可行情况。

然后整除分块。
我们可以直接搞出L/x相同的一段x，然后判断是否L/x<R/x，如果是则x的倍数在[L,R]中，差分即可。
但是还有一种情况没考虑到：L的>R-L+1的因数。
这样使得L/x=R/x且x的倍数出现在(L,R)中。
这部分直接枚举因数即可。
时间复杂度为:$O(n\sqrt{n})$

---

Code

#include<bits/stdc++.h>
using namespace std;
int c[200010],n,m;
int main(){int x,y;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%d%d",&x,&y);for(int j=1;j<=sqrt(x);j++)if(x%j==0){if(j>y-x) c[j]++,c[j+1]--;if(x/j!=j&&x/j>y-x) c[x/j]++,c[x/j+1]--; }for(int l=1,r;l<=x;l=r+1){//cout<<x<<" "<<y<<" "<<l<<" "<<r<<endl;r=min(x/(x/l),y/(y/l));//cout<<x<<" "<<y<<" "<<l<<" "<<r<<endl;if(x/l<y/l) c[l]++,c[r+1]--;//,cout<<l<<" "<<r+1<<endl;}c[x+1]++;c[y+1]--;}int ans=0;for(int i=1;i<=m;i++){ans+=c[i];printf("%d\n",ans);}
}

这篇关于Atcoder【arc068E】Snuke Line的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---