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

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

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

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

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

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

以下是代码:

#include
     
      //离散化+权值线段树求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]
      
       >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;    }