【前缀中位数】

题目描述

给定一个长度为 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:

 

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

3 Comments

  • image

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

      image

      @YYY 窝巢为啥我的归并线段树跑了TLE……果然是神犇与蒟蒻的差距吗OrzOrzOrz

        image

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

评论太激烈有些评论需要亲动动手指翻页

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

*