boj 67

Description
虽然没看过，但是ACMaryland知道这部电影，因为燕姿那首《我也很想他》。但今天我们不是要探讨这部电影，也不是这首歌，我们要来寻找自己的世界中心:-) 古人曾告诉我们，世界是平的。其实，每个人心中都有自己对世界的定义。经常看到一句话，我和你的世界，就像两条平行线，永远没有交集。于是，ACMaryland决定，定义这个虚拟世界为一条直线。 在这个世界里，ACMaryland想要寻找自己心中的世界中心，因此ACMaryland首先定义了自己所在的位置为0坐标点。然后要如何找到这个中心呢？ACMaryland找到了他的大牛室友，即将飞赴US攻读PHD学位的XiaoXi，XiaoXi所学专业是WSN（不是猥琐男哦），无线传感器网络。 Xiaoxi帮助ACMaryland在世界上布置了很多个传感器，每个传感器将会返回它所在的坐标值。但因为每个传感器返回的时间不一致，Xiaoxi帮助ACMaryland做了一个系统，这个系统支持两种操作： 1、输入两个整数，1 X，接收某个传感器返回的坐标值X； 2、输入一个整数，2，根据当前已收集的坐标值，计算并输出世界中心； 特别注意，ACMaryland定义自己的世界中心为已收集坐标值序列的中位数。 现在，一切都已就绪，一起开始寻找那个世界中心吧，在那未知的中心里呼唤爱情:-) 

Input
多组测试数据 对于每组测试数据： 第1行： 一个整数N（1 <= N <= 100,000），表示ACMaryland将会进行的操作次数 第2..N+1行： 每一行表示一次操作（第一次操作肯定是1类型）： 1、如果输入两个整数，1 X，接收某个传感器返回的坐标值X； 2、如果输入一个整数，2，根据当前已收集的坐标值，计算并输出世界中心； 

Output
如果当前操作输入为一个整数2，则打印输出当前世界中心，注意输出统一保留小数点后一位。 输入的最后是0，表示输入结束，这组数据不用处理。 

Sample Input

8 
1 2 
1 3 
2 
1 4 
2 
2 
1 -4 
2 


Sample Output

2.5 
3.0 
3.0 
2.5 


Hint
Sample 说明 首先输入两个数2,3，此时序列为{2, 3}，输入操作2，根据定义，可得中心为(2+3)/2 = 2.5，打印输出2.5；然后输入坐标4，序列更新为{2,3,4}，根据定义，可得中位数为3.0，根据输入的操作，则连续输出两个3.0；最后，输入坐标-4，根据定义，可得中位数为(2+3)/2 = 2.5，输出2.5。 中位数的定义： 对于一个含有m个元素的序列： 如果m为偶数，则中位数为第m/2个元素和第m/2+1个元素的平均值； 如果m为奇数，则中位数为第(m+1)/2个元素的值。 

Source
ACMaryland

 

用二叉排序树可以，为了熟悉线段树，用线段树做了，刚学，感觉做的很绕。。。

线段树：http://dongxicheng.org/structure/segment-tree/

！！！ps：oj上还有之前遇到的一些线段树的题目，可以再做下，加强学习

代码：

#include<iostream>
#include<algorithm>
using namespace std;
#define N 100005
struct Treenode{
	int l;
	int r;
	int c;
};
struct data{
	int v;
	int counter;
	int num;
};
data input[N+1];
int query[N+1];
int oper[N+1];
Treenode arr[3*(N+1)];

int cmp1(const data &a,const data &b)
{
	return a.v<b.v;
}
int cmp2(const data &a, const data &b)
{
	return a.counter<b.counter;
}
void bulid(int l,int r,int k)
{
	arr[k].l = l;
	arr[k].r = r;
	arr[k].c = 0;
	if(l==r)return ;
	int mid = (l+r)>>1;
	bulid(l,mid,2*k);
	bulid(mid+1,r,2*k+1);
}
void insert(int d,int k)
{
	if(arr[k].l==arr[k].r&&d==arr[k].l)
	{
		arr[k].c++;
		return;
	}
	int mid = (arr[k].l+arr[k].r)>>1;
	if(d>mid)
		insert(d,2*k+1);
	else
		insert(d,2*k);
	arr[k].c = arr[2*k].c+arr[2*k+1].c;
}
int search(int d,int k)
{
	if(arr[k].l==arr[k].r)
	{
		return arr[k].l;
	}
	if(d>arr[2*k].c)
		return search(d-arr[2*k].c,2*k+1);
	else
		return search(d,2*k);
}

int main()
{
	int n;
	while(~scanf("%d",&n))
	{
		if(n==0)break;
		int cnt = 1;
		bulid(1,n,1);
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&oper[i]);
			if(oper[i]==1)
			{
				scanf("%d",&input[cnt].v);
				input[cnt].counter = cnt;
				query[cnt] = input[cnt].v;
				cnt++;
			}
		}
		sort(query+1,query+cnt);
		sort(input+1,input+cnt,cmp1);
		for(int i=1;i<=cnt;i++)
			input[i].num = i;
		sort(input+1,input+cnt,cmp2);
		cnt = 0;
		for(int i=1;i<=n;i++)
		{
			if(oper[i]==1)
				insert(input[++cnt].num,1);
			else
			{
				if(cnt%2==1)
					printf("%.1f\n",(double)query[search(cnt/2+1,1)]);
				else
				{
					printf("%.1f\n",(double)(query[search(cnt/2,1)]+query[search(cnt/2+1,1)])/2);
				}
			}
		}
	}
}