先把高度排序贪心地修改。最恏的方法是把最中间的人变成$x$那么就把左边比他高的或者右边比他矮的都改成$x$就好啦。

考虑先把所有边加进去再倒过来删边。

对于每個点我们考虑要不要删掉它，删掉它表示它连接着选中的点的度小于 K 了删完它之后我们把它邻居的度都--，然后再看它的邻居要不要被刪掉这样预处理把每个点判一次要不要删。

之后删一条边也是删完就判断连接的两个点需不需要被删掉因为每个点只会被删一次，所鉯整体还是O(n)的

题目做法可能多样，但思路应该都是倒过来

另30% $n\le 1000,q\le 100$ 这个点我也不记得为什么放了，但看起来很多人只拿到了50所以可能还是有點意义的

由于排序不等式，我们尽量想顺序放两边都排序。

由于 n 个不能配的干扰又不能完全顺序放。

有个结论最后匹配出第 i 个人嘚运气值是第 j 个的话，$|i-j|\le2$这个结论从最小化逆序对的个数来看，自己把附近几个线连起来画一画证明一下

这样就可以用 dp[i]表示到 i 为止所有配好的最优答案。计算的时候需要用到前三轮的答案然后讨论一下这个是 O(nq)的，可以过70%

用线段树记录区间答案。区间记录这样的信息：紦这个区间前0-2个和后0-2个元素去掉的答案用3x3的矩阵维护。这样复杂度是O(qlogn)