P3871 [TJOI2010]中位数

    • 852通过
    • 2K提交
  • 题目提供者 elijahqi
  • 评测方式 云端评测
  • 标签 平衡树 排序 各省省选 2010 天津 O2优化
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

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

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    给定一个由N个元素组成的整数序列,现在有两种操作:

    1 add a

    在该序列的最后添加一个整数a,组成长度为N + 1的整数序列

    2 mid 输出当前序列的中位数

    中位数是指将一个序列按照从小到大排序后处在中间位置的数。(若序列长度为偶数,则指处在中间位置的两个数中较小的那个)

    例1:1 2 13 14 15 16 中位数为13

    例2:1 3 5 7 10 11 17 中位数为7

    例3:1 1 1 2 3 中位数为1

    输入输出格式

    输入格式:

    第一行为初始序列长度N。第二行为N个整数,表示整数序列,数字之间用空格分隔。第三行为操作数M,即要进行M次操作。下面为M行,每行输入格式如题意所述。

    输出格式:

    对于每个mid操作输出中位数的值

    输入输出样例

    输入样例#1: 复制
    6
    1 2 13 14 15 16
    5
    add 5
    add 3
    mid
    add 20
    mid
    
    输出样例#1: 复制
    5
    13
    

    说明

    对于30%的数据,1 ≤ N ≤ 10,000,0 ≤ M ≤ 1,000

    对于100%的数据,1 ≤ N ≤ 100,000,0 ≤ M ≤ 10,000

    序列中整数的绝对值不超过1,000,000,000,序列中的数可能有重复

    每个测试点时限1秒

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