正文

分析

先抄个形式化题意：

给定数轴上的 $n$ 条线段。

允许进行如下操作：

• 选出两条线段 $(l_i,r_i)$ 和 $(l_j,r_j)$。
• 把它们的四个端点重新任意配对，形成两条新的线段。

接下来有 $q$ 次询问。每次给出一个 $k_i$，要求求出：
最少需要多少次操作，才能让场上存在一个大小为 $k_i$ 的线段子集，使得其中任意两条线段都有交。

所谓“使得子集中的任意两条线段都有交”，也就是说使得子集中的线段都可以覆盖同一点。

于是，我们可以将这道题视作一道点的覆盖问题。

因此我们考虑一个点位置为 $p$，线段 $(l,r)$ 的分布情况也就只剩下了三类，这里分成下面三种：

1. 点 $p$ 被线段 $(l,r)$ 包含，即 $l\le p\le r$；
2. 点 $p$ 在线段 $(l,r)$ 左侧包括 $p=l$，即 $p\le l$；
3. 点 $p$ 在线段 $(l,r)$ 右侧包括 $p=r$，即 $p\ge r$。

如图：

设一类线段个数为 $X$，二类线段个数为 $R$，三类线段个数为 $L$，覆盖点 $p$ 的操作次数为 $Step_p$。

首先，如果我们需要让 $Step_p$ 最少，花费为 $0$ 的一类线段直接选。

其次，如果一类线段数量不够，那么就只能进行操作：
显而易见地，为了让操作得到的两条线段覆盖点 $p$，我们只能选择二类线段 $(l_i,r_i)$ 与三类线段 $(l_j,r_j)$ 各一条进行操作，“为什么”这种问题可以自己动手解决有脑就行。

因此，最终的 $Step_p$ 可以这么算：

思路

我们为了让 $Step_p$ 最少，显然 $X$ 是要最大的。

考虑到对于每一个点的 $X$ 是不变的，所以每个点 $X$ 都是可以提前预处理出来的。

但是有两个很大的问题是：

1. 点的值域很大 $(1\le l_i < r_i \le 10^9)$：很显然，我们肯定不能够对于每个点直接处理。
2. 我们选定的点 $p$ 并不一定可以让 $k_i$ 条线段覆盖点 $p$，此时情况为 $2\cdot \min(L,R)+X<k_i$，这里线段最多覆盖点 $p$ 的数即为 $2\cdot \min(L,R)+X$。为什么可以自己想一下。

第一个问题：

我们不一定关心的是每一个点，从点回归到线段上来。通过类似离散化的思路，我们发现只需要考虑线段的端点即可，例如本题的样例：

就可以近似变成↓

然后我们就可以得到一个类似扫描线的做法（就是只考虑线段的端点即可，端点的总数是 $2n$）。详细节见代码，具体怎么实现还是要靠自己感悟的。

第二个问题：

因为我们已经处理出了 $X$，所以我们可以处理出线段最多覆盖点 $p$ 的数，即 $2\cdot \min(L,R)+X$，然后所得到的 $X$ 可以被所有 $2\cdot \min(L,R)+X\ge k_i$ 的询问作为备选方案。
（举个例子：如果线段最多覆盖点 $p$ 的数为 $6$，那么点 $p$ 就可以是 $k_i=1,2,3,4,5,6$ 的询问所使用）。

有一个技巧：因为线段数量 $1\le n\le 2\times 10^5$，所以我们可以直接开一个线段数量大小的数组 $cnt$，将线段最多覆盖点 $p$ 的数为下标并赋值为 $X$，即 $cnt_{2\cdot \min(L,R)+X}=X$，最后再对数组 $cnt$ 做一个后缀最大值。

所以此时 $cnt_i$ 表示的意义就是至少可以覆盖 $i$ 条线段的所有点中最多的一类线段个数。

最后得到的询问答案即为：

代码

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
typedef pair<int,int> pii;
const int N=1e6+10;
const int M=2e3+10;
const int mod=1e9+7;
const int inf=1e17;
struct node{
	int l,r;
};
bool cmp(node x,node y){
	return x.l<y.l;
}
int n,Q;
node a[N];
priority_queue<int,vector<int>,greater<int>> q;
int cnt[N];
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>Q;
	for(int i=1;i<=n;i++){
		cin>>a[i].l>>a[i].r;
	}
	sort(a+1,a+n+1,cmp);
	int X=0,L=0,R=n; 
	for(int i=1;i<=n;i++){
		int x=a[i].l;
		while(!q.empty()&&x>q.top()){
			X--;
			L++;
			cnt[2*min(L,R)+X]=max(X,cnt[2*min(L,R)+X]);
			q.pop();
		}
		R--;
		X++;
		cnt[2*min(L,R)+X]=max(X,cnt[2*min(L,R)+X]);
		q.push(a[i].r); 
	}
	for(int i=n;i>=0;i--){
		cnt[i]=max(cnt[i],cnt[i+1]);
	}
	while(Q--){
		int k;
		cin>>k;
		int ans=((k-cnt[k])/2)+((k-cnt[k])%2);
		cout<<max(ans,0ll)<<' ';
	}
	return 0;
}

时间复杂度 $O(n\log n)$，$\log n$ 的瓶颈在于排序和堆。

另外提供一组调试样例：

Input:

6 6
1 10
2 9
3 8
4 7
5 6
11 12
1 2 3 4 5 6

Answer:

0 0 0 0 0 1