AtCoder Regular Contest 068E：Snuke Line

题目传送门：https://arc068.contest.atcoder.jp/tasks/arc068_c

题目翻译

直线上有\(0～m\)这\(m+1\)个点，一共有\(m\)辆火车。第\(i\)辆火车只会在\(i\)的倍数点上停靠，所有车都从\(0\)号点出发。

一共有\(n\)个商品，第\(i\)个商品只会在\(l_i～r_i\)号点出售，问你对于每辆火车，在可以停靠的站里，可以买到的商品种类数。

\(m\leqslant 10^5,n\leqslant 3*10^5\)。

题解

对于长度大于等于\(i\)的区间，肯定会对\(i\)号火车有贡献。长度小于\(i\)的，我们用树状数组差分查找就行了。

因为所有站点总和为\(mlogm\)，所以时间复杂度为\(mlog^2m\)。

时间复杂度： \(O(mlog^2m)\)

空间复杂度：\(O(m)\)

代码如下：

#include <cstdio>

#include <vector>

using namespace std;

#define low(i) ((i)&(-(i)))

const int maxm=1e5+5;

int n,m,cnt;

vector<int>range[maxm];

vector<int>::iterator it;

int read() {

	int x=0,f=1;char ch=getchar();

	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;

	for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';

	return x*f;

}

struct TreeArray {

	int c[maxm];

	void change(int pos,int v) {

		for(int i=pos;i<=m;i+=low(i))

			c[i]+=v;

	}

	int query(int pos) {

		int res=0;

		for(int i=pos;i;i-=low(i))

			res+=c[i];

		return res;

	}

}T;

int main() {

	cnt=n=read(),m=read();

	for(int i=1;i<=n;i++) {

		int l=read(),r=read();

		range[r-l+1].push_back(l);

	}

	for(int i=1;i<=m;i++) {

		int ans=cnt;

		for(int pos=i;pos<=m;pos+=i)

			ans+=T.query(pos);

		for(it=range[i].begin();it!=range[i].end();it++)

			T.change(*it,1),T.change((*it)+i,-1),cnt--;

		printf("%d\n",ans);

	}

	return 0;

}