rt，常见做法是 $O(n\log n)$ 的，预处理是 $O(L)$ 的，感觉这个数据范围下这个复杂度没必要 2s？