AT2300 Snuke Line
为什么你们不是主席树就是树状数组,发一个数论分块做法。
链接:https://www.luogu.com.cn/problem/AT2300
题目描述:有一趟列车有\(M+1\)个车站，从\(0\)到\(M\)编号。有\(N\)种商品，第\(i\)种只在编号\([li,ri]\)的车站出售。一辆列车有一个预设好的系数\(d\)，从\(0\)出发，只会在\(d\)的倍数车站停车。对于\(d\)从\(1\)到\(M\)的列车，求最多能买到多少种商品。
题解:可以发现，对于一个\(i\)，要满足\(l_{i}<=x\times d<=r_{i}\)就会产生贡献。
\(\qquad \qquad \qquad \qquad l_{i}<=x\times d<=r_{i}\)
\(\qquad \qquad \qquad \qquad \lceil \frac{l_{i}}{d} \rceil<=x<=\lfloor \frac{r_{i}}{d} \rfloor\)
\(\qquad \qquad \qquad \qquad \lfloor \frac{l_{i}-1}{d} \rfloor<x<=\lfloor \frac{r_{i}}{d} \rfloor\)
\(\qquad \qquad \qquad \qquad \lfloor \frac{l_{i}-1}{d} \rfloor<\lfloor \frac{r_{i}}{d} \rfloor\)
上述式子可以数论分块，对于每一种不同的\(i\)，差分即可得到答案。
#include<iostream>
using namespace std;
int l[1000001],r[1000001],sum[1000001];
int main()
{
int n,m,last;
cin>>n>>m;
for (int i=1;i<=n;++i)
{
cin>>l[i]>>r[i];
l[i]--;
for (int j=1;j<=l[i];j=last+1)
{
last=min(l[i]/(l[i]/j),r[i]/(r[i]/j));
if (l[i]/j<r[i]/j)
{
sum[j]++;
sum[last+1]--;
}
}
sum[l[i]+1]++;
sum[r[i]+1]--;
}
for (int i=1;i<=m;++i)
{
sum[i]+=sum[i-1];
cout<<sum[i]<<endl;
}
return 0;
}