$Set$中自带的$prev(Set.lower$ _ $bound())$和$next(Set.lower$ _ $bound())$学习

众所周知：二分查找的题目我们可以快速调用$STL$的$lower$ _ $bound()$和$upper $_$ bound()$以$O(logn)$的复杂度快速查找目标值。借此引入$prev(Set.lower$ _ $bound())$和$next(Set.lower$ _ $bound())$,我们可以调用$prev(Set.lower$ _ $bound())$快速查找$Set.lower$ _ $bound()$的前一个数的下标,同理$next(Set.lower$ _ $bound())$快速查找$Set.lower$ _ $bound()$的后一个数下标。

真题练习： [上海理工大学校内选拔赛L] 剪绳子

本题可以将$double$化为整数那么整数范围即是$0$~$1000000$,那么本题可以转化为二分查找,每次$C$命令即在$Set$中插入一个浮点转化为$6$位的整数,而$A$命令即在$Set$中查询当前数所在块长度,此时会用到$prev(Set.lower$ _ $bound())$和$next(Set.lower$ _ $bound())$。

• 参考代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
    set<int>S;
    S.insert(0);
    S.insert(1000000);
    int t;
    cin>>t;
    while(t--){
        string op,s;
        cin>>op>>s;
        int len=s.size();
        int ans=0;
        for(int i=0;i<s.size();i++){
            if(isdigit(s[i]))
            ans=(ans<<1)+(ans<<3)+(s[i]^48);
        }
        if(op[0]=='A'){
            int res;
            if(ans)
                res = *S.lower_bound(ans) - *prev(S.lower_bound(ans));
            else res = *next(S.lower_bound(ans)) - *S.lower_bound(ans);//这种情况是因为存在查询为0.00000的情况
            printf("%d.%05d\n",res/100000,res%100000);
        }
        else{
            S.insert(ans);
        }
    }
    return 0;
}