离散化

今日做题时，偶遇巨大数据，拼尽全力无法ac，才明白用map离散化被卡了，看来是不得不学一下了。

map实现离散化

map基于红黑树实现，每次查询是O(logn)的，因此被卡掉了，不多说了。

STL实现离散化

只需三步轻松实现。
（1）sort函数排序
（2）unique函数去重
（3）二分索引(lower_bound()函数)

	sort(b+1,b+1+tot);  //第一步：排序 
	res=unique(b+1,b+1+tot)-(b+1);  //unique函数计算出去重后的元素个数，存在res中
	for(register int i=1;i<=n;i++) {
		a[i]=lower_bound(b+1,b+1+res,a[i])-b;  //lower_bound函数进行索引 
	}
	return 0;
}

哈希表实现离散化

哈希表如果构造得好可以实现接近O(1)查询，后面再开一篇写哈希表。