知道了调出来了
```cpp
set<pair<long long, int> >::iterator it = lower_bound(s.begin(), s.end(), make_pair(h[i], i));
```
复杂度是 $O(nlogn)$ 的
```cpp
set<pair<long long, int> >::iterator it = s.lower_bound(make_pair(h[i], i));
```
改成这样，就是 $O(logn)$ 的
by FCB_Yiyang2006✈ @ 2021-10-10 00:49:39
求大神解释
by FCB_Yiyang2006✈ @ 2021-10-10 00:49:59
std::set 的 iterator 不是 LegacyRandomAccessIterator，在 std::lower_bound 中自增调用次数为线性。
by andyli @ 2021-10-10 01:06:08
建议优化下常数,尤其是pair等stl的东西,而且还要带上set,常数比较大。
你试试自己在本地测一组 $10^6$ 的数据,如果在10s内跑完了,那就是常数问题。否则就是复杂度问题。
by xh39 @ 2021-10-10 04:04:53
@[FCB_Yiyang2006✈](/user/149301) 借楼%
by FCB_1899 @ 2021-10-10 08:49:37
问了一个大佬，普通 $lowerbound$ 的实现是二分查找，而 $set$ 的迭代器只能 $++$ 或 $--$，所以复杂度是 $nlogn$
而 $set$ 自带的 $lowerbound$ 是用平衡树实现的，所以复杂度是 $logn$ 的。
by FCB_Yiyang2006✈ @ 2021-10-10 15:11:28
@[201811101400_145_214](/user/87799)
@[andyli](/user/84282)
谢谢大佬
by FCB_Yiyang2006✈ @ 2021-10-10 15:12:07
@[FCB_1899](/user/209561) orz
by FCB_Yiyang2006✈ @ 2021-10-10 15:12:24