Submission #4024901

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
template <typename T> void read(T &t) {
	t=0; char ch=getchar(); int f=1;
	while ('0'>ch||ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
	do {(t*=10)+=ch-'0';ch=getchar();} while ('0'<=ch&&ch<='9'); t*=f;
}
typedef long long ll;
const int maxn=(2e6)+10;
int n,m,lazy[maxn],sz[maxn],ans,cnt;
ll tr[maxn];
struct node { int l,r; };
vector<node> g[maxn/4];
void pushdown(int root) {
	if (!lazy[root]) return;
	tr[root*2]+=(ll)lazy[root]*sz[root*2];
	tr[root*2+1]+=(ll)lazy[root]*sz[root*2+1];
	lazy[root*2]+=lazy[root];
	lazy[root*2+1]+=lazy[root]; lazy[root]=0;
}
void build(int l,int r,int root) {
	sz[root]=r-l+1; if (l==r) return;
	int mid=(l+r)/2; build(l,mid,root*2); build(mid+1,r,root*2+1);
}
void add(int L,int R,int l,int r,int root) {
	if (L<=l&&r<=R) {
		tr[root]+=sz[root]; lazy[root]++; return;
	} pushdown(root);
	int mid=(l+r)/2;
	if (L<=mid) add(L,R,l,mid,root*2);
	if (mid<R) add(L,R,mid+1,r,root*2+1);
	tr[root]=tr[root*2]+tr[root*2+1];
}
int query(int x,int l,int r,int root) {
	if (l==r) return tr[root];
	pushdown(root);
	int mid=(l+r)/2;
	if (x<=mid) return query(x,l,mid,root*2);
	return query(x,mid+1,r,root*2+1);
}
int main() {
	//freopen("1.txt","r",stdin);
	read(m); read(n);
	int x,y;
	for (int i=1;i<=m;i++) {
		read(x); read(y);
		g[y-x+1].push_back((node){x,y});
	} build(1,n,1);
	for (int i=1;i<=n;i++) {
		for (int j=0;j<g[i].size();j++)
			add(g[i][j].l,g[i][j].r,1,n,1),m--;
		ans=m;
		for (int j=i;j<=n;j+=i)
			ans+=query(j,1,n,1);
		printf("%d\n",ans);
	}
	return 0;
}

Submission Info

Judge Result