P3769 人类智慧乱搞 题解【[CH弱省胡策R2] TATT】

· · 题解

我们充分发扬人类智慧：

将所有点按照字典序（就是 a 先，相同的再看 b，以此类推）排序，就是要求排好序的点集的 LIS

根据数学直觉，答案中的两个点在数组中肯定不会离得太远

所以我们只取每个点向前的 7500 个点来计算答案

这样速度快得飞起，在 n=50000 的时候都可以在 1s 内卡过，虽然时限 2s