问题2535--原谅逆序对

2535: 原谅逆序对

时间限制: 2 Sec  内存限制: 128 MB
提交: 45  解决: 4
[状态] [讨论版] [提交] [命题人:]
题目描述
绿绿学姐从小便十分喜欢学习。
小学三年级时,她的体育老师给她布置了一个作业,逆序数问题。
绿绿的参考书显示:
对于一个序列a,当一对下标(i,j)满足i<j且a[i]>a[j],就称(i,j)为一个逆序对。
序列a的所有不同逆序对的个数,就称为逆序数。
如何求出一个序列的逆序数,就叫做逆序数问题。
绿绿花了十分钟完全解决了作业之后,她想到了一个新问题,如何求出一个序列的第k小的逆序对?
现在她把这个问题交给你来解决。

逆序对(a,b)小于(c,d)当且仅当 a<c 或者 a==c且b<d。
请注意,逆序对是一对下标。
输入
一个整数T(<=40),表示测试数据的组数,随后有T组数据。
每组数据有两行,第一行有两个整数n(<=10^5),k(>=1),表示序列长度和要求的逆序对,第二行有n个整数,表示序列a (对任意i都满足 1 <= a[i] <= 10^6)。
如果不存在第k小的逆序对,输出"E.M.T."(不包含引号)。
输出
每组数据输出两个空格隔开的整数i,j,表示(i,j)是第k小的逆序对。
样例输入 Copy
3
5 1
1 2 3 4 5
5 1
5 4 3 2 1
5 5
5 4 3 2 1
样例输出 Copy
E.M.T.
1 2
2 3
来源/分类