考了一道抽象 AGC，属实是逆天了。
description
令 \(M\) 为一正整数。
给出 \(2 N\) 个整数 \(a_1, a_2, \ldots , a_{2N}\)，满足 \(0 \le a_i < M\)。
你需要把这 \(2 N\) 个整数分成 \(N\) 对，每一对 \((x, y)\) 的权值为 \((x + y) \bmod M\)。
令一种分配方案的权值为每一对的权值的最大值，请问权值最小的分配方案的权值为多少？
- \(1 \le N \le {10}^5\)，\(1 \le M \le {10}^9\)，\(0 \le a_i < M\)。
solution
首先我们发现可以二分答案，但是 Check 里面是一个 \(n^3\) 的一般图最大匹配，并且这个做法十分没有可拓展性。
于是你考虑对于每个 \(i\)，寻找一个可行的最远的 \(j\)，将其匹配，发现复杂度很复杂，于是考虑能不能找规律。
将样例描述一下，匹配对实际上是 \((1, 4), (2, 3), (5, 6)\)，发现类似于划分为两个段，使得两个段从中间往两边扩展匹配。并且你考虑将 \(3000\) 的样例跑一下前几项，发现也符合这个规律，所以开始考虑高妙结论。
考虑枚举前一段和后一段的分界点，然后分别扩展，这样你就得到了一个 \(O(n^2)\) 做法，测了测 \(100000\) 的大样例，发现过了，于是果断考虑优化。但是发现区间贡献是一个类似于区间平移并且对应和 \(mod\) 的一个东西，这感觉用数据结构不太能优化（我更改必须更改到每一个结点 pushup 才是对的），于是不会了。
题解说分界点的值也有单调性，并且弱化限制条件，并且发现第一个段的和 \(< m\)，第二个段的和 \(> m\)，于是你就二分一下，就过了。
属实是纯神了。
标签：发现,le,匹配,T1,抽象,权值,并且,考虑,打爆 From： https://www.cnblogs.com/alexande/p/18472244