中位数 | Dy_ClearSunlight

题目链接：中位数
题目标签：线段树
题意：有一个长度为N的序列，要求输出前k个的中位数（1<=k<=(N+1)/2）。
- 题目分析：这道题如果暴力来做，N<=1e9，必TLE。所以本题主要考察了用线段树来模拟数组的理解+一点离散化。
- 大体思路：原始数列用a数组来存，用b数组来将a数组排序去重（sort,unique），如果不懂unique请点击这。再用一个线段树来模拟b数组，从1开始，找到a[i]在b数组中的位置，让线段树中的一个变量来存在b数组中对应元素出现的个数，让对应位置的这个变量+1，如果i为奇数，那就找到中位数并输出。
- 关于如何找中位数：按照我们的方法，当我们枚举到i时，前i个元素出现的次数已经被我们记录，既然b数组已经升序排序了，那我们就直接输出b数组中第（i/2+1）大的元素就行了。
  - 如何用线段树来查找第（i/2+1）大的元素：我们用l来存对应b数组位置的值，r为以当前节点为父亲的子节点包含的最大元素值，mid为以当前节点为父亲的 _左_ 子节点包含的最大元素值，那我们查找时，只要判断一下（i/2+1）是否比当前节点的mid大就行了，如果小于等于mid，说明在左子树，如果大于mid,说明在右子树，那就继续向下查找。
    - 需要注意的一点是：如果要查找右子树，需要将number(初始为（i/2+1）)减去当前节点的mid，笔者因语文不太好，~~无法清楚明白地解释原因，请读者自行理解~~。。。

AC代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define gc getchar()
#define Maxn 100010
using namespace std;
int sc() { //快读 
	int xx=0,ff=1; char cch;
	while(cch<'0'|| cch>'9') {
		if(cch=='-') ff=-ff; cch=gc;
	}
	while(cch>='0'&& cch<='9') {
		xx=xx*10+(cch-48); cch=gc;
	}
	return xx*ff;
}
int n;
int a[Maxn],b[Maxn];
int L[Maxn*4],R[Maxn*4],Mid[Maxn*4],num[Maxn*4]; //线段树 
namespace DY {
	void build(int k,int l,int r) { //建树 
		L[k]=l; R[k]=r; Mid[k]=l+r>>1;
		if(l== r) return ; //说明是最后的叶节点，跳出 
		build(k<<1, l, Mid[k]);
		build(k<<1|1, Mid[k]+1, r);
	}
	void modify(int k,int now) { //修改 
		num[k]++; //num++ 
		if(L[k]== R[k]) return ;
		if(now<=Mid[k]) modify(k<<1, now);
		if(now>Mid[k]) modify(k<<1|1, now);
	}
	int query(int k,int number) { //查询 
		if(L[k]==R[k]) return L[k]; //返回当前节点的值 
		if(number<=num[k<<1]) return query(k<<1, number);
		else return query(k<<1|1, number-num[k<<1]);
	}
	void main() {
		n=sc(); //输入 
		for(int i=1; i<=n; i++) {
			a[i]=sc();
			b[i]=a[i];
		}
		build(1,1,n); //建树 
		sort(b+1,b+n+1); //升序排序 
		int len=unique(b+1,b+n+1)-b; //去重 
		for(int i=1; i<=n; i++) {
			int now=lower_bound(b+1,b+len+1,a[i])-b; //找到a[i]在b[]的位置 
			modify(1,now); //将其对应num++ 
			if((i&1)==1) { //如果i为奇数 
				printf("%d\n",b[query(1,i/2+1)]); //输出第i/2+1大的元素 
			}
		}
	}
};
int main() {
	DY::main();
	return 0;
}

RP++

RP++