我提交了28次、花费了三个小时,用血与眼泪告诫大家:
STL中的upper_bound函数,不能用于查找set里的元素,否则复杂度会从 O(log2n)O(log_2n)O(log2n) 退化成 O(n)O(n)O(n) !
upper_bound
所以只能使用set的成员函数(方法) upper_bound !!
lower_bound同理!!!
lower_bound
示例:
// auto tmp=upper_bound(mp[a[x]].begin(),mp[a[x]].end(),x); // 上面写法会多T五个点,bound里面套set复杂度会退化成O(n)! auto tmp=mp[a[x]].upper_bound(x); //直接调用成员函数!