容易想到可以分治。但纯分治 O(qn2log⁡n)O(q n^2 \log n)O(qn2logn)，只能得 15pts15pts15pts。 发现有区间 maxmaxmax，套上 ST 表。时间复杂度 O(qnlog⁡n)O(qn \log n)O(qnlogn)，得到 76pts76pts76pts。 容易发现既然有了 ST 表，加上区间划分，容易想到倍增分块。时间复杂度 O(nq+nlog⁡n)O(nq + n \log n)O(nq+nlogn)，AC 100pts100pts100pts。 upd on 2025/12/06：记得卡常，要不然会 TLE 几个点。