1. 首页
  2. 代码宅, 可持久化数据结构

【前缀中位数】

题目描述

给定一个长度为 N 的序列 A,标号为 1~N ,其第 i 个数字为 Ai 。要求一个长度同样为 N 的序列 B 。已知,Bi 为序列 A 中 1~i 所有数的中位数。

定义中位数:对于长度为 2m 的序列,中位数为第 m 小的数,对于长度为 2m+1 的序列,中位数为第 m+1 小的数。

输入格式

第一行一个整数 N ,表示序列 A 长度。
接下来一行有 N 个用空格隔开的数,第 i 个数表示 A

输出格式

输出 N 行,每行一个数,第 i 行的数表示 Bi 。

样例数据 1

输入

3
1 2 3

输出

1
1
2

备注

【数据范围】
对于 30% 的数据有:N<=200;
对于 60% 的数据有:N<=2000;
对于 100% 的数据有:N<=200000,所有数字在 10范围内。

第一次写主席树没加读优常数各种巨大982ms险过QAQ 后来还是照着YYY大神的模板重写了一遍只用了300+ms(窝巢我原来写的真的是主席树!?)瞬间感受到了蒟蒻和神犇的差距……

不说了接下来上模板TAT:

 

评分 0, 满分 5 星
0
0
看完收藏一下,下次也能找得到
上一篇:
:下一篇

3 条评论

gravatar

*

  1. YYY 1

    窝巢为啥我的权值线段树跑了800+ms..果然是神犇与蒟蒻的差距吗OrzOrz

    #-49楼
    Google Chrome 43.0.2357.130Windows 7
    回复
    stdKonjac真是太蠢辣QAQ
    1. @YYY 窝巢为啥我的归并线段树跑了TLE……果然是神犇与蒟蒻的差距吗OrzOrzOrz

      Google Chrome 44.0.2403.155unknow
      回复
      stdKonjac真是太蠢辣QAQ
      1. YYY 1

        @UNknown Orz我连什么是归并线段树都不知道…OrzOrz

        Google Chrome 43.0.2357.130Windows 7
        回复
        stdKonjac真是太蠢辣QAQ