统计长度为5的上升序列个数，
容易想到O(n^2)的dp
f[k,i]:=Σf[k-1,j] (1<=j<i,a[i]>a[j])
ans：=Σf[5,i]
但是显然会超时，需要考虑优化
怎样快速找到所有比当前高度小的状态的和呢？
答案很显然：树状数组
考虑到这题每个数<=10^9，我们要将其离散化，再映射到树状数组上
注意这题的最终答案爆int64，所以要用到高精度
1 var f,tr:array[0..5,0..50010] of int64; //tr[i,j]表示树状数组，序列长度为i时，末尾离散化后高度为j；树状数组不会爆int64 2 ans,d:array[0..100] of integer; 3 a,b,c:array[0..50010] of longint; 4 len,k,n,i,j:longint; 5 6 function lowbit(x:longint):longint; 7 begin 8 exit(x and (-x)); 9 end;10 11 procedure add(z:int64); //高精度加法12 var i,la,w,x:longint;13 begin14 fillchar(d,sizeof(d),0);15 la:=0;16 while z<>0 do17 begin18 la:=la+1;19 d[la]:=z mod 10;20 z:=z div 10;21 end;22 if la>len then len:=la;23 inc(len);24 w:=0;25 for i:=1 to len do26 begin27 x:=w+d[i]+ans[i];28 ans[i]:=x mod 10;29 w:=x div 10;30 end;31 if ans[len]=0 then dec(len);32 end;33 34 function sum(p,q:longint):int64;35 begin36 sum:=0;37 while p>0 do38 begin39 sum:=sum+tr[q,p];40 p:=p-lowbit(p);41 end;42 end;43 44 procedure work(p,q,z:int64); //将当前状态加入树状数组45 begin46 while p<=n do47 begin48 tr[q,p]:=tr[q,p]+z;49 p:=p+lowbit(p);50 end;51 end;52 53 begin54 while not eof do55 begin56 readln(n);57 fillchar(c,sizeof(c),0);58 fillchar(tr,sizeof(tr),0);59 fillchar(f,sizeof(f),0);60 for i:=1 to n do61 begin62 read(a[i]);63 b[i]:=i;64 end;65 readln;66 sort(1,n);67 c[b[1]]:=1;68 k:=1;69 for i:=2 to n do //离散化，注意重复的标相同的号70 if a[i]=a[i-1] then71 c[b[i]]:=c[b[i-1]]72 else begin73 inc(k);74 c[b[i]]:=k;75 end;76 fillchar(ans,sizeof(ans),0);77 len:=1;78 for i:=1 to n do79 begin80 f[1,i]:=1;81 work(c[i],1,1);82 for j:=2 to 5 do83 begin84 f[j,i]:=sum(c[i]-1,j-1); //dp85 if f[j,i]>0 then work(c[i],j,f[j,i]); 86 end;87 if f[5,i]>0 then add(f[5,i]);88 end;89 for i:=len downto 1 do90 write(ans[i]);91 writeln;92 end;93 end.
总复杂度为O(nlogn)
质量很高的一道题
var f,tr:array[0..5,0..50010] of int64; //tr[i,j]表示树状数组，序列长度为i时，末尾离散化后高度为j；树状数组不会爆int64
ans,d:array[0..100] of integer;
a,b,c:array[0..50010] of longint;
len,k,n,i,j:longint;
function lowbit(x:longint):longint;
begin
exit(x and (-x));
end;
procedure add(z:int64); //高精度加法
var i,la,w,x:longint;
begin
fillchar(d,sizeof(d),0);
la:=0;
while z<>0 do
begin
la:=la+1;
d[la]:=z mod 10;
z:=z div 10;
end;
if la>len then len:=la;
inc(len);
w:=0;
for i:=1 to len do
begin
x:=w+d[i]+ans[i];
ans[i]:=x mod 10;
w:=x div 10;
end;
if ans[len]=0 then dec(len);
end;
function sum(p,q:longint):int64;
begin
sum:=0;
while p>0 do
begin
sum:=sum+tr[q,p];
p:=p-lowbit(p);
end;
end;
procedure work(p,q,z:int64); //将当前状态加入树状数组
begin
while p<=n do
begin
tr[q,p]:=tr[q,p]+z;
p:=p+lowbit(p);
end;
end;
begin
while not eof do
begin
readln(n);
fillchar(c,sizeof(c),0);
fillchar(tr,sizeof(tr),0);
fillchar(f,sizeof(f),0);
for i:=1 to n do
begin
read(a[i]);
b[i]:=i;
end;
readln;
sort(1,n);
c[b[1]]:=1;
k:=1;
for i:=2 to n do //离散化，注意重复的标相同的号
if a[i]=a[i-1] then
c[b[i]]:=c[b[i-1]]
else begin
inc(k);
c[b[i]]:=k;
end;
fillchar(ans,sizeof(ans),0);
len:=1;
for i:=1 to n do
begin
f[1,i]:=1;
work(c[i],1,1);
for j:=2 to 5 do
begin
f[j,i]:=sum(c[i]-1,j-1); //dp
if f[j,i]>0 then work(c[i],j,f[j,i]);
end;
if f[5,i]>0 then add(f[5,i]);
end;
for i:=len downto 1 do
write(ans[i]);
writeln;
end;
end.