题目描述

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

我来吐槽

*

*

取消

*

2位绅士参与评论

  1. YYY08-17 22:48 回复

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

    • UNknown08-18 00:10 回复

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

      • YYY08-18 14:17 回复

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