P2343 宝石管理系统

    • 224通过
    • 776提交
  • 题目提供者 韦索宇韦
  • 评测方式 云端评测
  • 标签 平衡树 洛谷原创
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    GY君购买了一批宝石放进了仓库。有一天GY君心血来潮,想要清点他的宝石,于是把m个宝石都取出来放进了宝石管理系统。每个宝石i都有一个珍贵值vi,他希望你能编写程序查找到从大到小第n珍贵的宝石。但是现在问题来了,他非常不小心的留了一些宝石在仓库里面,有可能要往现有的系统中添加宝石。这些宝石的个数比较少。他表示非常抱歉,但是还是希望你的系统能起作用。

    输入输出格式

    输入格式:

    第一行一个整数m,q,表示已经取出来的宝石个数以及接下来的查询或插入操作个数。

    第二行m个整数,表示这m个宝石的珍贵值。

    以下q行,每行两个整数c,n,

    若c=1(即询问),则输出当前第n珍贵的宝石,

    若c=2(即插入),则往系统中插入珍贵值为n的宝石。

    输出格式:

    对于每个c=1(询问),输出当前第n珍贵的宝石的珍贵值vi。

    输入输出样例

    输入样例#1: 复制
    5 3
    1 3 2 5 6
    1 3
    2 4
    1 6
    
    输出样例#1: 复制
    3
    1

    说明

    对于50%的数据,没有c=2的情况;

    对于100%的数据,m<=100000,c=2的情况不超过10000,q<=30000

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。