ABC 241D - Sequence Query（multiset）

new knowledge（stl）

multiset位于库中，可以看成一个序列，
插入一个数，删除一个数都可以在O(logn)的时间内完成，
能时刻保证序列中的数是有序的，
而且序列中可以存在重复的数。

https://atcoder.jp/contests/abc241/tasks/abc241_d

题目大意：
先给定一个空数组a，有三种操作
第一种：1 x表示插入x这个数据
第二种：2 x k表示在数组a中查找到<=x的第k个数字（按从大到小的顺序）
第三种：3 x k表示在数组a中查找到>=x的第k个数字（按从小到大的顺序）

Sample Input 1  
11
1 20
1 10
1 30
1 20
3 15 1
3 15 2
3 15 3
3 15 4
2 100 5
1 1
2 100 5
Sample Output 1  
20
20
30
-1
-1
1

这个题目还需要使用到lower_bound和upper_bound等stl的相关知识。
正解如下：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL N=200200,M=2002;
int main()
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    LL T=1;
    //cin>>T;
    while(T--)
    {
        LL n;
        cin>>n;
        multiset<LL> ms;//内部有序
        for(LL i=1;i<=n;i++)//n次操作
        {
            LL op;
            cin>>op;
            if(op==1)//插入操作
            {
                LL x;
                cin>>x;
                ms.insert(x);
            }
            else if(op==2)//<=x的第k个数字，它得从当前位置往前找(并不是从第一个位置往后找，别想歪了)
            {
                LL x,k;
                cin>>x>>k;
                auto it=ms.upper_bound(x);//查找大于目标值的第一个元素
                while(k&&it!=ms.begin())
                {
                    k--;//先参与运算再递减
                    it--;//指针一直往前寻找
                }
                if(k==0) cout<<*it<<endl;
                else cout<<"-1"<<endl;
            }
            else if(op==3)//>=x的第k个数字
            {
                LL x,k;
                cin>>x>>k;
                auto it=ms.lower_bound(x);//查找大于等于目标值的第一个元素
                k-=1;
                while(k&&it!=ms.end())
                {
                    --k;
                    it++;//指针一直往后寻找
                }
                if(it!=ms.end()) cout<<*it<<endl;//到不了最后即为查找成功
                else cout<<"-1"<<endl;//找不到位置
            }
        }
    }
    return 0;
}