【AtCoder - 2300】Snuke Line（树状数组）

#include <cstdio>
#include <algorithm>
#define N 100001
using namespace std;
int n,m;
struct souvenir{
	int l,r,len;
	bool operator <(const souvenir &b){
		return len<b.len;
	}
}s[N*3];
int c[N];
int get(int i){
	int ans=0;
	for(;i;i-=i&(-i))ans+=c[i];
	return ans;
}
void add(int i,int v){
	for(;i<=m;i+=i&(-i))c[i]+=v;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1,l,r;i<=n;++i){
		scanf("%d%d",&l,&r);
		s[i]=(souvenir){l,r,r-l+1};
	}
	sort(s+1,s+1+n);
	for(int i=1,j=1;i<=m;++i){
		while(j<=n&&s[j].len<i){
			add(s[j].l,1);
			add(s[j].r+1,-1);
			++j;
		}
		int ans=n-j+1;
		for(int k=i;k<=m;k+=i)
			ans+=get(k);
		printf("%d\n",ans);
	}
	return 0;
}