矩阵（matrix）
时间限制：1Sec 内存限制128MB
【题目描述】
给定一个n*n的矩阵A，第i行第j列的值a[i,j]= i^2+100000 × i + j^2 - 100000 × j + i × j，求出矩阵中第m小的的值
【输入】
两个正整数n,m，表示矩阵大小和要找第m小的值
【输出】
一行，表示第m小的值
【样例输入1】
5 10
【样例输出1】
-99939
【样例输入2】
3 9
【样例输出2】
200013
【数据范围】
100%1<=n<=50000,1<=m<=n*n
【提示】
每一列的数都是从小到大单调递增的,用两个二分，一个二分枚举答案，一个二分用来验证答案是否正确。
为什么超时了？
var
n,i:longint;
m:int64;
f:boolean;
function cal(i,j:int64):int64;
begin
if i=0 then exit(-(1 shl 60));
exit(i*i+100000*i+j*j-100000*j+i*j);
end;
begin
assign(input,'matrix.in');reset(input);
assign(output,'matrix.out');rewrite(output);
readln(n,m);
f:=true;
for i:=1 to n do
if m-i>0 then m:=m-i else
begin
f:=false;
break;
end;
if not f then begin writeln(cal(m,n-i+m)); halt; end;
for i:=n-1 downto 1 do
if m-i>0 then m:=m-i else
begin
f:=false;
break;
end;
writeln(cal(n-i+m,m));
close(input);close(output);
end.

求助！

提示已经讲得很明白了
这个矩阵一行中从左到右递增，一列中从上到下递增。右下角为最大值，二分一个值，枚举每一行并在其中二分小于其的数值，保持小于其的数低于M个。时间复杂度O(nlognlogn)
至于你贴出的程序，看不懂在干什么，而且随便一个样例大概都能说明是错的。

此贴已沦陷

再发一遍我怕又给删了
我已经申请人工恢复了。。。度娘说有违规URL或联系方式？？

【Copy】
好吧。。大概懂你程序意义了，你是不是觉得因为数据范围的限制所以主对角线平行的斜对角的每层就是递增了？
首先我要抱歉的是我确实一拍脑门就觉得这程序错了，但没有经过实际检验。
可能这东西靠小数据对拍你看不出来，但是经过数学计算，很容易发现问题。
中间过程不推了，那么我直接讲结论了，矩阵范围为n时，(1,1)处的数为3，(n-1,n)处的数为(n-1)^2+n^2+n(n-1)-10^5，那么随便代个n比如n=50000，(n-1,n)处的值为7499750001，这违反了之前所说的你遵循的规律。
小数据看不出，大数据基本上就是错的了。
重复一下做法：
因为A(i,j)=i^2+(j+i-10^5)*j，所以每一行从左到右递减（貌似上一楼口误了），可二分。
顺便附程序：
var
n,m,i:Longint;
L,R,Mid:Int64;
function A(const i,j:Int64):Int64;
begin
exit(i*i+j*j+i*j+(i-j)*100000)
end;
function Ct(const x:Int64):Longint;
var i,l,r,m:Longint;
begin
Ct:=0;
for i:=1 to n do
begin
l:=0;
r:=n;
while l<r do begin
m:=(l+r+1)>>1;
if A(i,m)>=X then l:=m
else r:=m-1
end;
inc(Ct,n-l)
end
end;
begin
assign(input,'matrix.in'); reset(input);
assign(output,'matrix.out'); rewrite(output);
read(n,m);
L:=-int64(1)<<50;
R:=-L;
while L<r do begin
Mid:=(L+R+1)div 2;
if Ct(Mid) else R:=Mid-1
end;
write(L);
close(input); close(output)
end.
（退役后悲惨地做水题机）

var
i:longint;
ab,n,m,l1,r1,mid1,tot,l,r,mid:int64;
function cal(i,j:int64):int64;
begin
if i=0 then exit(-(1 shl 60));
exit(i*i+100000*i+j*j-100000*j+i*j);
end;
begin
//assign(input,'matrix.in');reset(input);
//assign(output,'matrix.out');rewrite(output);
readln(n,m);
l:=-n*100000;
r:=n*n+n*100000+n*n*2;
while l<r do
begin
mid:=(l+r-1) div 2;
tot:=0;
for i:=1 to n do
begin
l1:=0;
r1:=n;
while l1<r1 do
begin
mid1:=(l1+r1+1) div 2;
if cal(mid1,i)<=mid then l1:=mid1+1 else r1:=mid1-1;
inc(ab);
end;
tot:=tot+l1;
end;
if tot>=m then r:=mid else l:=mid+1;
end;
writeln(l);
writeln(ab);
//close(input);close(output);
end.

@shyakocat
大神，我还是觉得有一点问题：
1、m应该是int64;
2、输大数的时候，还是会超时

我是shyakocat
那你常数优化一下就行了
{$OPTIMIZATION ON}
{$R-,Q-,S-}
var
n,i:Longint;
m,L,R,Mid:Int64;
function A(const i,j:Int64):Int64;inline;
begin
exit(i*i+j*j+i*j+(i-j)*100000)
end;
function Ct(const x:Int64):int64;inline;
var i,l,r,m:Longint;
begin
Ct:=0;
for i:=1 to n do
begin
l:=0;
r:=n;
while l<r do begin
m:=(l+r+1)>>1;
if A(i,m)>=X then l:=m
else r:=m-1
end;
inc(Ct,n-l)
end
end;
begin
assign(input,'matrix.in'); reset(input);
assign(output,'matrix.out'); rewrite(output);
read(n,m);
L:=A(1,n);
R:=A(n,1);
while L<r do begin
Mid:=(L+R+1)div 2;
if Ct(Mid)<M then L:=Mid
else R:=Mid-1
end;
write(L);
close(input); close(output)
end.
首先显然第1行第n个就是最小值，第n行第1个就是最大值，那么二分区间就是[A(1,n),A(n,1)]
注意：我这边虽然有编译开关，但都是NOI系列赛事（包括noip）中规定的
其一，NOI系列赛事中，很可能是开O2的，而一般在Windows的fp里你是不会开的。。那么，你在前面加上一句{$OPTIMIZATION ON}或者{$OPTIMIZATION LEVEL2}就是O2，LEVEL3就是O3，你酌情使用。
其二，对于小而常用的函数，你可以函数内敛（inline）来加速。对于旧版本的fp你需要加一句{$INLINE ON}，但现在NOI使用fp2.6.4，不用加这句编译开关，把上述的两个函数后面加上inline;这样可以酌情把运算放到寄存器里，不必每次耗时地到内存里读取。
其三，使用{$R-,Q-,S-}来加速，这三个开关在noi系列赛事中是给pascal默认加上的，不然pascal的速度和c++会有太的常数大差距。这三个的意思分别是关闭数组溢出检查、关闭运算溢出检查、关闭栈溢出检查。也就是说，pascal本来数组溢出（201），运算溢出（215），栈溢出（202）会有检查并有错误码，但是现在我们关闭了他，这大大加速了你程序的运行速度。而且c++语言是默认没有这种检查的，c++是不会报错并认为它合法的，所以c++很快。有时你看到c++的程序报错了其实那不是c++的报错，而是Windows的报错，很多操作系统不允许访问这个程序以外的其他内存。
日常中还有很多常数优化的技巧。。我也只是退役了把技巧传给他人而已

你可以照这张图的改。。
讲优化原理的那个贴被度娘吞了

试试看