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)号点出售，问你对于每辆火车，在可以停靠的站里，可以买到的商品种类数。

(mleqslant 10^5,nleqslant 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
",ans);
	}
	return 0;
}