Atcoder Regular Contest#068 E.Snuke Line

~{→看不见LaTex格式的Dalao们请刷新本页Thanks♪(･ω･)ﾉ←}~

2019寒假集训题

E.Snuke Line

题面

Snuke has decided to play a game, where the player runs a railway company. There are $M+1$ stations on Snuke Line, numbered $0$ through $M$. A train on Snuke Line stops at station $0$ and every $d$-th station thereafter, where $d$ is a predetermined constant for each train. For example, if $d=3$, the train stops at station $0, 3, 6, 9$, and so forth.

There are $N​$ kinds of souvenirs sold in areas around Snuke Line. The $i​$-th kind of souvenirs can be purchased when the train stops at one of the following stations: stations $l_i,l_i+1,l_i+2,…r_i​$.

There are M values of d, the interval between two stops, for trains on Snuke Line: $1, 2, 3, …, M$. For each of these $M$ values, find the number of the kinds of souvenirs that can be purchased if one takes a train with that value of d at station $0$. Here, assume that it is not allowed to change trains.

---

简要翻译

有$m$个点集，第$i$个点集包含$0$至$m$中编号是$i$的倍数的点。

给定$n$个区间，对于每个点集，求出有多少个区间包含点集内的至少一个点。

---

或者说是：

有$n$个区间，现在询问你对于$1\le i\le m$的每个$i$，有多少个区间至少包含一个$i$的倍数？

---

Input

输入的标准格式如下：

N M
l1 r1
:
lN rN

---

Output

输出答案$M$行。第$i$-th行包含停在$d$站的答案。

---

Sample Input 1

3 3
1 2
2 3
3 3

---

Sample Output 1

3
2
2

---

Sample Input 2

7 9
1 7
5 9
5 7
5 9
1 1
6 8
3 4

---

Sample Output 2

7
6
6
5
4
5
5
3
2

---

Hint

$1\le M\le 10^5$

$1\le N\le 3×10^5$

$1\le l_i\le r_i\le M$

---

我们如果按题目去题意去做，我也不知道怎么想。

我们反着思考，如果一个区间中没有$i​$的倍数，那么它一定是被相邻的两个$i​$的倍数夹在中间了，或是在最大的$i​$的倍数的右边了。

所以我们可以先读入所有的数据再用可持久化线段树离线处理啦！

---

Code

#include<bits/stdc++.h>
using namespace std;
int read()
{
	int x = 0, w = 0;
	char ch = 0;
	while (!isdigit(ch)) {w |= ch == '-'; ch = getchar();}
	while (isdigit(ch)) {x = (x << 3) + (x << 1) + ch - '0'; ch = getchar();}
	return w ? -x : x;
}
const int M=100010;
const int N=300010;
struct seg_tree
{
	int cnt,l,r;
}t[N<<5];
int cnt_sgt,p[M],n,m;
struct rg
{
	int l,r;
	friend bool operator < (rg a,rg b)
	{
		return a.l<b.l;
	}
}rg[N];
void pushup(int root)
{
	t[root].cnt=t[t[root].l].cnt+t[t[root].r].cnt;
}
void insert(int &root,int l,int r,int x)
{
	t[++cnt_sgt]=t[root],root=cnt_sgt;
	if(l==r) 
	{
		t[root].cnt++;
		return;
	}
	int mid=l+r>>1;
	if(x<=mid) insert(t[root].l,l,mid,x);
	else insert(t[root].r,mid+1,r,x);
	pushup(root);
}
int query(int root1,int root2,int l,int r,int ll,int rr)
{
	if(ll<=l&&r<=rr) return t[root2].cnt-t[root1].cnt;
	int mid=l+r>>1;
	int s=0;
	if(ll<=mid) s+=query(t[root1].l,t[root2].l,l,mid,ll,rr);
	if(rr>mid) s+=query(t[root1].r,t[root2].r,mid+1,r,ll,rr);
	return s;
}
int main(int argc, char const *argv[])
{
	n=read(),m=read();
	for(int i=1;i<=n;++i) rg[i].l=read(),rg[i].r=read();
	sort(rg+1,rg+1+n);
	int q=1;
	for(int i=1;i<=m;++i)
	{
		p[i]=p[i-1];
		while(rg[q].l==i) insert(p[i],1,m,rg[q++].r);
	}
	printf("%d\n",n);
	for(int i=2;i<=m;++i)
	{
		int answer=n,j;
		for(j=i;j<=m;j+=i) answer-=query(p[j-i],p[j-1],1,m,j-i+1,j-1);
		if(j-i+1<=m) answer-=query(p[j-i],p[m],1,m,j-i+1,m);
		printf("%d\n",answer);
	}
	return 0;
}