题意：
给定一个N*N矩阵，其中Aij =i2 +100000 × i + j2 - 100000 × j + i × j。
求矩阵中第K大的数。
题解：
自然的想法还是算出来所有的Aij，排序，然后二分找第K大的数，时间复杂度又来打了O（N2），肯定会超时。
注意观察Aij =i2 +100000 × i + j2 - 100000 × j + i × j。
这个式子 Aij关于i单调增，所以没有必要算出所有的Aij，对每一列找出Aij小于X的数的个数（lower_bound），然后所有的列一共有cnt个小于X的数，如果cnt>=K，说明这个X一定是太大了，并且X不是可行解！
当然，这里也可找出Aij小于等于X的数的个数，这时候要判断cnt<K
,如果小于K，说明X取得太小了。X不是可行解！
其实这两种判断方法就是lower_bound和upper_bound，选一个自己喜欢的就可以了。
和上一道题类似，都是查找第K大的值。二分再套个二分。上一道题可以用直接库函数，这里不能而已。
这里给出lower_bound思想的一种代码！
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>long long const INF=0x3f3f3f3f3f;//4个3f大概是10亿多，题目最大也是十亿级别甚至更高的。5个3f大概是2000亿。using namespace std;
long long N,M;long long cal(long long i,long long j)
{return i*i+100000*i+j*j-100000*j+i*j;
}bool C(long long x)
{long long sum=0;for(long long j=1;j<=N;j++){long long l=0,r=N+1;while(r-l>1)//求>=x的最小位置{long long mid=(r+l)/2;if(cal(mid,j)<x)l=mid;else r=mid;}sum+=l;}return sum>=M;
}int main()
{int T;cin>>T;while(T--){scanf("%l64d%l64d",&N,&M);long long lb=-1*INF,ub=INF;//好像没有边界？直接放的宽宽的。while(ub-lb>1){long long mid=(ub+lb)/2;if(C(mid))ub=mid;else lb=mid;}cout<<lb<<endl;}}