统计长度为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 begin 14 fillchar(d,sizeof(d),0); 15 la:=0; 16 while z<>0 do 17 begin 18 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 do 26 begin 27 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 begin 36 sum:=0; 37 while p>0 do 38 begin 39 sum:=sum+tr[q,p]; 40 p:=p-lowbit(p); 41 end; 42 end; 43 44 procedure work(p,q,z:int64); //将当前状态加入树状数组 45 begin 46 while p<=n do 47 begin 48 tr[q,p]:=tr[q,p]+z; 49 p:=p+lowbit(p); 50 end; 51 end; 52 53 begin 54 while not eof do 55 begin 56 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 do 61 begin 62 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] then 71 c[b[i]]:=c[b[i-1]] 72 else begin 73 inc(k); 74 c[b[i]]:=k; 75 end; 76 fillchar(ans,sizeof(ans),0); 77 len:=1; 78 for i:=1 to n do 79 begin 80 f[1,i]:=1; 81 work(c[i],1,1); 82 for j:=2 to 5 do 83 begin 84 f[j,i]:=sum(c[i]-1,j-1); //dp 85 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 do 90 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.