这个结论还是太牛逼了。
首先你考虑一个事情，假设我目前存在一个重排列的方案，存在一列 \(i\)，使得 \(a_i, b_i\) 都不选进答案，那么必然可以将其中较大的那一个移动到一个合适的位置使得获得 \(\max(a_i, b_i)\) 的贡献，因为我们无需考虑较小数的贡献。
所以此时 \(\max (a_i, b_i)\) 必然被选进答案中。
然后最非人类的一步是，你要想到按 \(a\) 排序，但是我想到了。
于是你考虑哪些 \(\min(a_i, b_i)\) 能够被选上，此时若这个数在 \(b\) 里，那么之前选的在 \(b\) 中的数必须要全部小于它，此时由于 \(\max(a_i, b_i) = a_i\)，而 \(a_i\) 排序，所以必选。
若这个数在 \(a\) 里，那么必然会被选上因为 \(a\) 已经排序，但是此时 \(b_i\) 若也要被选那么之前选的 \(b\) 必然都要小于 \(b_i\)。
两种策略结合起来，求 LIS 即可。
这种题一般都是猜个结论然后构造证明，直接想构造有点非人类。