提供一个E题O(nlogn)的做法。 右边部分就不说了。 左边部分，要查询[1,i]中最右边的值>h的位置。线段树维护最大值，[1,i]在线段树中分成最多logn段。从右到左的扫这些段，如果这个段的最大值<=h，那么整段都不满足，继续下一段。如果这个段的最大值>h，那么答案一定在这个段内，在这个段内继续二分，复杂度也是O(logn），因此总的复杂度是O(nlogn)。 代码： int ask(int L, int R, int h, int l, int r, int rt) { if (L <= l && r <= R) { if (mx[rt].h <= h) return 0; if (l == r) return l; int mid = (l+r)/2; if (mx[rt<<1|1] > h) return ask(L,R,h,mid+1,r,rt<<1|1); return ask(L,R,h,l,mid,rt<<1); } int mid = (l+r)/2, ans = 0; if (mid < R) ans = ask(L,R,h,mid+1,r,rt<<1|1); if (ans == 0 && L <= mid) ans = ask(L,R,h,l,mid,rt<<1); return ans; }