Description(嘛,找不到文字题面)
Analysis
因为数字是从小到大插入的,所以我们可以构造出最终序列,然后O(NlogN)求最长上升子序列。
关键是构造出最终序列。
2B青年:我会平衡树!
平衡树模拟插入,求出最终序列,虽然可以过,但是代码量和时间不尽人意。
下面来讲一下文艺的做法吧...
我们发现,将整个序列反过来做,如果当前数插入的位置定了,将不会再受到影响。
而这样子就可以用树状数组维护,首先将所有的位置都设为一,每次插入一个数,相当于找到最前面的一段区间,它们的和=当前数插入的位置(设为L[1,i]),则这个插入的数的位置就是i。插入之后,将i这个位置置为零(用过了)。
可以通过二分来找到这个i,更好的方法是通过二进制(刚学)。
看下面的代码:
function get(k:longint):longint; var ans,cnt,i:longint; begin ans:=0; cnt:=0; for i:=20 downto 0 do begin ans:=ans+1 shl i; if (ans>=n) or (cnt+c[ans]>=k) then ans:=ans-1 shl i else cnt:=cnt+c[ans]; end; exit(ans+1); end;
这是用树状数组的定义来加速处理的方法,i从20开始取是因为数据范围<=100000(理解不了可以看一下树状数组的定义)。
接下来我们就可以还可以再用树状数组维护一个区间最大值,当然直接套O(NlogN)的最长上升子序列的传统做法也可以,不过树状数组比较方便。
上代码:
var i,j,k,n,tmp:longint; c,cnt,pos,ans,fa:array[0..100000] of longint; function getfa(t:longint):longint; begin if fa[t]=t then exit(t); fa[t]:=getfa(fa[t]); getfa:=fa[t]; end; function lowbit(x:longint):longint; begin exit(x and (-x)); end; function max(a,b:longint):longint; begin if a>b then exit(a) else exit(b); end; procedure change(x,delta:longint); begin while x<n do begin c[x]:=max(c[x],delta); x:=x+lowbit(x); end; end; function getmax(x:longint):longint; begin getmax:=0; while x>0 do begin getmax:=max(getmax,c[x]); x:=x-lowbit(x); end; end; function get(k:longint):longint; var ans,cnt,i:longint; begin ans:=0; cnt:=0; for i:=20 downto 0 do begin ans:=ans+1 shl i; if (ans>=n) or (cnt+c[ans]>=k) then ans:=ans-1 shl i else cnt:=cnt+c[ans]; end; exit(ans+1); end; begin readln(n); for i:=1 to n do begin read(pos[i]); inc(pos[i]); inc(c[i]); if i+lowbit(i)<=n then c[i+lowbit(i)]:=c[i+lowbit(i)]+c[i]; end; for i:=n downto 1 do begin j:=get(pos[i]); cnt[i]:=j; while j<n do begin dec(c[j]); j:=j+lowbit(j); end; end; for i:=1 to n do c[i]:=0; for i:=1 to n do begin tmp:=getmax(cnt[i]-1)+1; ans[i]:=max(ans[i-1],tmp); change(cnt[i],tmp); end; for i:=1 to n do writeln(ans[i]); end.