有没有最长不上升序列nlogn 的算法（信息学）

有没有最长不上升序列nlogn 的算法（信息学）

有

用单调队列+二分。

用D[I] 记录 长度为I的序列的最小结尾值

易证知

D[I]为上升序列。

用二分查找找出当前A[I]的位置

并更新D[I]值

function min(x:longint):longint;
var s,w,mid:longint;
begin
s:=0;w:=l;
while s<w do
begin
mid:=(s+w) div 2;
if d[mid]<x then s:=mid+1 else w:=mid;
end;
exit(s);
end;
begin
readln(n,k);
for i:=1 to n do read(a[i]);
l:=0;d[0]:=-maxlongint;
for i:=1 to k do
begin
if a[i]>d[l] then
begin
inc(l);
d[l]:=a[i];
end
else
begin
t:=min(a[i]);
if a[i]<d[t] then d[t]:=a[i];
end;
end;

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息