SSOJ2616数字排名
2353+
作者：crxis 发布：2017-11-29 分类：离散化
题目大意：有n个数，m个询问，每次回答数x是第几大或者第x大的是哪个数。
输入
第一行：2个整数n和m
第二行：n个整数
接下来m行，每行2个数o和x，o=1请回答x（保证是n个数中的一个）是第几大，o=2请回答第x大的是哪个数，不存在第x大，输出“ERR”。
输出
q行，每行一个回答
样例输入
5 3
1 2 3 2 4
1 2
2 1
2 5
样例输出
3
4
ERR
提示
1<=o<=2；n个数，每个数的绝对值不超过20000000；5<=n、m<=200000
(10个点数据范围：5, 10, 100, 500, 1000, 5000, 10000, 50000, 100000, 150000, 200000)
解题思路
排序后去重，很容易就处理出第x大的是哪个数，我们可以预先放入p数组中。
对于回答x是第几大，我们可以在p数组中遍历查找，找到后该位置即是答案。为了提高速度，我们可以采用二分查找；为了更方便处理这个映射关系，我们还可以使用哈希表。
当然，这个只是简单的离散化，我们可以直接排序后模拟处理就行。
程序实现
排序后离散化：p数组记录去重后的数组，方便寻找第x大；x数组记录的是询问的排名或者询问的数字的排名。26行中，d[i].i < 0表示是询问的编号的相反数，因为需要回答排名，我们可以直接把排名填进去。对于每个询问，我们可以离线回答。
二分查找第x大：
哈希回答x的排名：
暴力遍历查找第x大：
