Description：

$n$ 个人在一个环上接力，每个人有一个区间，保证两两不包含，问保证第 $i$ 个人参与的情况下最少几个人能覆盖整个环。

$1\leqslant n\leqslant 2\times 10^5$

Solution：

要保证一个人一定参与，只要让他开始或结束就好了，看上去非常像一个数据结构，但其实正解是倍增，因为区间两两不包含，所以按左端点排序右端点也是递增的，那么就找一个开始最晚的作为下一个，这样下一个是确定的，于是就预处理出从 $i$ 开始走 $2^k$ 个人后的那个人以及这是走的距离，然后最后枚举每个人作为第一个人，倍增出最后一个总长度不超过 $m$ 的位置，顺便统计一下途中换过了几个人即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 200010

struct seg

{

	int l,r;

	int id;

	bool operator < (const seg &b)const

	{

		return l < b.l;

	}

}s[MAXN << 1];

bool cmp_l(seg a,seg b){return a.l < b.l;}

int f[MAXN][19];

long long g[MAXN][19];

int ans[MAXN];

int main()

{

	scanf("%d%d",&n,&m);

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

	{

		scanf("%d%d",&s[i].l,&s[i].r);

		s[i].id = i;

	}

	sort(s + 1,s + 1 + n,cmp_l);

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

	{

		if(s[i].r < s[i].l)s[i].r += m;

	}

	for(int i = 1;i <= n;++i)s[n + i] = (seg){s[i].l + m,s[i].r + m,s[i].id};

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

	{

		f[i][0] = upper_bound(s + 1,s + 1 + n * 2,(seg){s[i].r,0,0}) - s - 1;

		g[i][0] = s[f[i][0]].r - s[i].r;

		if(f[i][0] > n)f[i][0] -= n;

	}

	for(int k = 1;k <= 18;++k)

	{

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

		{

			f[i][k] = f[f[i][k - 1]][k - 1];

			g[i][k] = g[i][k - 1] + g[f[i][k - 1]][k - 1];

		}

	}

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

	{

		int cur = s[i].r - s[i].l;

		int p = i;

		int res = 0;

		for(int k = 18;k >= 0;--k)

		{

			if(cur + g[p][k] < m)

			{

				cur += g[p][k];

				p = f[p][k];

				res += (1 << k);

			}

		}

		++res;

		ans[s[i].id] = res + 1;

	}

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

	{

		printf("%d ",ans[i]);

	}

	puts("");

	return 0;

}