本文共 918 字，大约阅读时间需要 3 分钟。

AT2300 Snuke Line

为什么你们不是主席树就是树状数组,发一个数论分块做法。

链接:

题目描述:有一趟列车有\(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
   
    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
   

转载地址：https://www.cnblogs.com/zhouhuanyi/p/16983610.html 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！