1. 题目

传送门=￣ω￣=

2. 题解

这题我是查树状数组出来的。。。
然后我就当作 splay 的练手题了
蛮水的
搞个能保存每个数字出现了多少次的 splay 查 kth 就行了
也就是一边插入一遍查 kth((i+1)/2)

代码：

#include <bits/stdc++.h>
using namespace std;
template<typename _Tp>inline void IN(_Tp&dig)
{
    char c;dig=0;
    while(c=getchar(),!isdigit(c));
    while(isdigit(c))dig=dig*10+c-'0',c=getchar();
}
struct N{int d,cnt,siz,f,s[2];N(){d=cnt=siz=f=s[0]=s[1]=0;}}e[100005];
int root,tsiz;
bool pos(int a){return e[e[a].f].s[1]==a;}
void update(int a){e[a].siz=e[e[a].s[0]].siz+e[e[a].s[1]].siz+e[a].cnt;}
void rot(int a)
{
    int f=e[a].f,g=e[f].f,p=pos(a),q=pos(f);
    e[f].s[p]=e[a].s[!p],e[a].s[!p]=f,e[f].f=a;
    if(e[f].s[p])e[e[f].s[p]].f=f;
    if(e[a].f=g)e[g].s[q]=a;
    update(f),update(a);
}
void splay(int a)
{
    while(e[a].f)
    {
        if(e[e[a].f].f)
        {
            if(pos(a)^pos(e[a].f))rot(a);
            else rot(e[a].f);
        }
        rot(a);
    }
    root=a;
}
void insert(int d,int f,int&a)
{
    if(!a){a=++tsiz,e[a].d=d,e[a].siz=e[a].cnt=1,e[a].f=f,splay(a);return;}
    e[a].siz++;
    if(e[a].d==d)e[a].cnt++,splay(a);
    else if(d<e[a].d)insert(d,a,e[a].s[0]);
    else insert(d,a,e[a].s[1]);
}
int query_kth(int k,int a)
{
    if(e[e[a].s[0]].siz+1<=k&&k<=e[e[a].s[0]].siz+e[a].cnt)
        {splay(a);return e[a].d;}
    if(e[e[a].s[0]].siz+e[a].cnt<k)
        return query_kth(k-e[e[a].s[0]].siz-e[a].cnt,e[a].s[1]);
    return query_kth(k,e[a].s[0]);
}
int n;
int main()
{
    IN(n);
    for(int i=1,a;i<=n;i++)
    {
        IN(a),insert(a,0,root);
        if(i&1)printf("%d\n",query_kth((i+1)>>1,root));
    }
    return 0;
}

另：肚子好饿啊！