正題

題目鏈接:
https://www.luogu.com.cn/problem/AT2300
https://atcoder.jp/contests/arc068/tasks/arc068_c

---

題目大意

有$m$個車站，$n$種禮品，第$i$種可以在$[l_i,r_i]$的車站買到，第$d$輛車會近過編號為$d$的倍數的車站，對于每個$d$最多能買到多少件禮物。

---

解題思路

考慮對于一組$[L,R]$能否買到禮物$d$，我們不難發現需要滿足條件$?\frac{L?1}{d}?=?\frac{R}{d}?$即可。
學習了莫比烏斯反演的話不難發現對于$?\frac{L?1}{d}?$和$?\frac{R}{d}?$只有不超過$2(\sqrt{L?1}+\sqrt{R})$種取值，而對于相同的取值的$d$一定是一個區間。

我們進行整除分塊，然后用差分進行區間加，時間復雜度$O(n\sqrt{m}+m)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; int m,n,a[101000]; int main() {scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){int L,R,l,r;scanf("%d%d",&L,&R);L--;for(l=1;l<=L;l=r+1){r=min(L/(L/l),R/(R/l));if(L/l!=R/l)a[l]++,a[r+1]--;}a[l]++;a[R+1]--;}for(int i=1;i<=m;i++){a[i]+=a[i-1];printf("%d\n",a[i]);} }

總結

以上是生活随笔為你收集整理的AT2300-[ARC068C]Snuke Line【整除分块】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。