题目描述
给定一个长度为 N 的序列 A,标号为 1~N ,其第 i 个数字为 Ai 。要求一个长度同样为 N 的序列 B 。已知,Bi 为序列 A 中 1~i 所有数的中位数。
定义中位数:对于长度为 2m 的序列,中位数为第 m 小的数,对于长度为 2m+1 的序列,中位数为第 m+1 小的数。
输入格式
第一行一个整数 N ,表示序列 A 长度。
接下来一行有 N 个用空格隔开的数,第 i 个数表示 Ai 。
输出格式
输出 N 行,每行一个数,第 i 行的数表示 Bi 。
样例数据 1
输入
3
1 2 3
1 2 3
输出
1
1
2
备注
【数据范围】
对于 30% 的数据有:N<=200;
对于 60% 的数据有:N<=2000;
对于 100% 的数据有:N<=200000,所有数字在 109 范围内。
第一次写主席树没加读优常数各种巨大982ms险过QAQ 后来还是照着YYY大神的模板重写了一遍只用了300+ms(窝巢我原来写的真的是主席树!?)瞬间感受到了蒟蒻和神犇的差距……
不说了接下来上模板TAT:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 |
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #define N 200001 #define Maxval 1000000001 using namespace std; int n,cnt,pos,a[N],root[N<<5]; struct node{int lson,rson,sum;}tree[N<<5]; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();} while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();} return x*f; } void newnode(int now) { root[now]=++cnt; tree[cnt]=tree[root[now-1]]; } void update(int rt,int L,int R,int val) { if(L==R){tree[rt].sum++;return;} int mid=(L+R)>>1; if(val<=mid) { tree[++cnt]=tree[tree[rt].lson]; tree[rt].lson=cnt; update(tree[rt].lson,L,mid,val); } if(val>mid) { tree[++cnt]=tree[tree[rt].rson]; tree[rt].rson=cnt; update(tree[rt].rson,mid+1,R,val); } tree[rt].sum=tree[tree[rt].lson].sum+tree[tree[rt].rson].sum; } void query(int left,int right,int L,int R,int pos) { if(L==R) {cout<<L<<endl;return;} int mid=(L+R)>>1; int now=tree[tree[right].lson].sum-tree[tree[left].lson].sum; if(now>=pos) query(tree[left].lson,tree[right].lson,L,mid,pos); if(now<pos) query(tree[left].rson,tree[right].rson,mid+1,R,pos-now); } void init() { n=read(); for(int i=1;i<=n;i++) { a[i]=read(); newnode(i); update(root[i],1,Maxval,a[i]); } } void ask() { for(int i=1;i<=n;i++) { pos=(i%2==0)?(i>>1):(i>>1)+1; query(root[0],root[i],1,Maxval,pos); } } int main() { freopen("T3.in","r",stdin); freopen("T3.out","w",stdout); init(); ask(); return 0; } |
3 Comments
窝巢为啥我的权值线段树跑了800+ms..果然是神犇与蒟蒻的差距吗OrzOrz
@YYY 窝巢为啥我的归并线段树跑了TLE……果然是神犇与蒟蒻的差距吗OrzOrzOrz
@UNknown Orz我连什么是归并线段树都不知道…OrzOrz