[洛谷P1168]中位数（Splay）/（主席树）

Description

给出一个长度为N的非负整数序列A[i]，对于所有1 ≤ k ≤ (N + 1) / 2，输出A[1], A[2], …, A[2k - 1]的中位数。即前1，3，5，……个数的中位数。

N ≤ 100000

Solution

这题方法很多，这里介绍splay的打法

求中位数即求第$(k+1)/$2小的数，用splay维护即可，只有2中操作：插入，旋转

在树上记录一个\(c(u)\)表示节点\(u\)的子树有几个节点，用来判断第n小

只要在插入和旋转的时候维护就行了

Code

#include <cstdio>

#include <algorithm>

#define lc(x) T[(x)][0]

#define N 100010

int n,tot,k[N],T[N][2],s[N],rt,fa[N];

void rotate(int p){

	int q=fa[p],y=fa[q],x=(T[q][1]==p);

	T[q][x]=T[p][x^1];fa[T[q][x]]=q;

	T[p][x^1]=q;fa[q]=p;

	fa[p]=y;

	if(y){

		if(T[y][0]==q) T[y][0]=p;

		else if(T[y][1]==q) T[y][1]=p;

	}

	s[p]=s[q];

	s[q]=s[T[q][0]]+s[T[q][1]]+1;//这里维护c(u)

}

void splay(int x){

	for(int y;y=fa[x];rotate(x))

		if(fa[y]) rotate((x==lc(y))==(y==lc(fa[y]))?y:x);

	rt=x;

}

void Insert(int x,int v){

	if(!rt){

		rt=++tot;

		s[rt]=1;

		k[rt]=v;

		return;

	}

	int y;

	while(y){

		y=T[x][k[x]<v];

		if(!y){

			y=++tot;

			k[y]=v;

			T[y][0]=T[y][1]=0;

			fa[y]=x;

			s[x]++;s[tot]++;//c(u)初始化

			T[x][k[x]<v]=y;

			break;

		}

		x=y;

	}

	splay(y);

}

int Find(int x){

	int r=0;

	for(int u=rt;;){

		if(r+s[T[u][0]]+1==x) return k[u];

		if(r+s[T[u][0]]+1<x) r+=s[T[u][0]]+1,u=T[u][1];

		else u=T[u][0];

	}

}

int main(){

	scanf("%d",&n);

	for(int i=1;i<=n;++i){

		int t;

		scanf("%d",&t);

		Insert(rt,t);

		if(i&1) printf("%d\n",Find((i>>1)+1));

	}

	return 0;

}