题意

有 $n$ 条线段，最多能选出 $m$ 条互不相交的线段。现在，你要在这 $n$ 条线段中选择 $\frac n 2$ 条线段，满足你最多可以在其中选出 $\frac m 2$ 条互不相交的线段。求构造方案。

题解

以下记元素个数 $\frac n 2$ 的集合为 $S$，个数为 $\frac m 2$ 的集合为 $T$。

考虑子任务五，这个线段之间要么相离、要么包含的关系可以抽象成一棵森林，其中每条线段的父亲节点为包含他的线段中最短的那个。

那么一条线段能被选入 $T$，当且仅当这条线段的所有后代都没有被选入 $T$。

贪心地想，我们肯定会选择 $\frac m 2$ 个叶子进入 $T$，那么他们所有的祖先都可以选入 $S$，且不会对 $T$ 产生任何影响。只要他们祖先集合的并的长度大于等于 $\frac n 2$ 就满足了条件。用一个线段树支持暴力修改、查询即可。

对于一般的情况，能不能创造出一些类似于森林的东西，满足一个节点被选择进入 $S$ 后，他的祖先或儿子就不能被选入 $T$ 了呢？

答案是肯定的。我们考虑计算 $m$ 的过程：将所有线段按 $r$ 排序，每次贪心地能取就取。对于两个相邻的被取入答案的线段 $l, r$，有 $[l+1, r-1]$ 中的线段在 $l$ 选入 $S$ 的情况下全都无法进入 $T$。

证明是显然的，$[l+1, r-1]$ 的线段全没被选择说明他们的左端点全都小于等于 $l$ 的右端点。而 $l$ 在他们的左边，说明 $l$ 的右端点更小，在 $S$ 中排完序后 $l$ 能进入 $T$，则 $[l+1, r-1]$ 都不能。

然后就简单了。我们挑 $\frac m 2$ 个“偏序区间”长度最大的被选择的点加入 $T$，并把他们的“偏序区间”中的元素加入 $S$ 即可。

代码

#include<bits/stdc++.h>
#define rep(i, j, k) for(int i=(j); i<=(k); ++i)
using namespace std;
const int N=1e5+7;
struct node{int l, r, id;}a[N];
int n, nxt[N];
vector<int> v, res;
signed main(){
  cin.tie(0)->sync_with_stdio(0);
  int t; cin>>t; 
  while(t--){
    cin>>n;
    rep(i, 1, n) cin>>a[i].l>>a[i].r, a[i].id=i;
    sort(a+1, a+n+1, [](const node x, const node y){return x.r<y.r;});
    int pre=0;
    rep(i, 1, n+1)
      if(i==n+1 || a[pre].r<a[i].l){
        if(pre) nxt[pre]=i-1, v.emplace_back(pre);
        pre=i;
      }
    sort(v.begin(), v.end(), [](int x, int y){return nxt[x]-x>nxt[y]-y;});
    rep(i, 0, v.size()/2-1) res.emplace_back(v[i]);
    rep(i, 0, v.size()/2-1){
      int x=v[i];
      if(res.size()==n/2) break;
      rep(j, x+1, nxt[x]){
        res.emplace_back(j);
        if(res.size()==n/2) break;
      }
    }
    for(auto x:res) cout<<a[x].id<<' '; cout<<'\n';
    res.clear(), v.clear();
  }
}