看了此题,发现是求中位数,自然而然的想到了求kth

求kth有多种,我用的是权值线段树,即记录x的个数,但,我们看题，发现a[i]可以高达1e9,一个数组是开不完的,

不过万幸的是n只到了1e5,而求kth只需要知道大小关系就行,不需要知道具体的值,所以,我们可以用离散化来搞定它！

这里说一下stable_sort,它其实跟sort差不多,不过区别在于相同元素sort后的值是一样的！所以stable_sort极适合用于离散化

那么问题来了,假如我们用离线算法,各种判断,骚操作,眼花缭乱,本蒟蒻的内心qwq 所以,我们可以考虑在线算法！

我们动态将此时的a[i] (离散化后) 的个数+1,然后每到i为奇数时我们就求出的(i+1)/2大的数即可了~

以下是代码: 

#include<bits/stdc++.h>//离散化+权值线段树求kth  using namespace std; const int N=1e5+1; long long a[N]; long long e[N],b[N]; int c[N]; int d[N<<2];
    inline long long read(){ long long X=0,w=0; char ch=0; while(!isdigit(ch)) {w|=ch=='-';ch=getchar();} while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar(); return w?-X:X;
    }//快读  inline bool kk(int x,int y){ return a[x]<a[y];
    }
    inline void up(int now,int l,int r,int x){
        d[now]++;//范围中有x的都加一,不用左儿子加右儿子那么麻烦~  if(l==r){ return;
        } int mid=((l+r)>>1); if(x<=mid){
            up(now<<1,l,mid,x);//向左查找  return;
        }
        up(now<<1|1,mid+1,r,x);//向右查找   }
    inline int kth(int now,int l,int r,int x){ if(l==r){ return l;
        } int ls=now*2; int mid=((l+r)>>1); if(d[ls]>=x){//如果前面的数的个数大于x  return kth(ls,l,mid,x);//向前搜   } return kth(ls|1,mid+1,r,x-d[ls]);//注意这里是x-d[ls],因为前半段有d[ls]个数,那么,kth在后半段的排名应为x-d[ls]  } int main(){ int n;
        n=read(); long long x; for(int i=1;i<=n;++i){
            a[i]=read();
            e[i]=a[i];//记录存值  c[i]=i;//用于之后离散化   }
        stable_sort(c+1,c+n+1,kk);//stable排序  for(int i=1;i<=n;++i){
            a[c[i]]=i;//离散化值,离散化后a[i]表示原来第i个数第a[i]大  } for(int i=1;i<=n;++i){
            b[a[i]]=e[i];//记录值,用于输出   } for(int i=1;i<=n;++i){
            up(1,1,1e5,a[i]);//a[i]加一  if(i%2){ int zhong=(i+1)>>1;
                printf("%lld\n",b[kth(1,1,1e5,zhong)]);
            } 
        } return 0;
    }