Bài toán: Tìm các số đặc biệt của dãy A cho trước

Bài toán: Tìm các số đặc biệt của dãy A cho trước
Bài toán : Cho dãy số nguyên A[1],A[2],,A[N] khác nhau đôi một (N<=10 5 ,1<=A[I]<=N).A[I] được gọi là một số đặc biệt đối với dãy số trên nếu A[I] thuộc ít nhất một dãy con tăng dài nhất của A.Ở đây xin nhắc lại một chút về định nghỉa dãy con tăng dài nhất,dãy con tăng dài nhất là dãy A[i 1 ],A[i 2 ],,A[ip] thỏa: 
• 1 ≤ i 1 < i 2 < < ip ≤ N. 
• A[i 1 ] < A[i 2 } <  < A[ip]. 
• P lớn nhất có thể được. 
Yêu cầu của bài toán là bạn phải chỉ ra tất cả các số đặc biệt của dãy A theo định nghĩa ở trên. 
Input : Dữ liệu vào từ file SUPERNUM.INP : 
•  Dòng đầu là số T (1 ≤ T ≤ 10) là số bộ test bạn phải giải quyết. 
•  T nhóm dòng sau,mỗi nhóm gồm 2 dòng: 
•  Dòng đầu là số N. 
•  Dòng thứ 2 chứa N số nguyên từ 1 tới N. 
Output : Dữ liệu ra ghi lên file SUPERNUM.OUT gồm T dòng,mỗi dòng ghi các số đặc biệt của bộ test tương ứng theo thứ tự tăng dần. 
SUPERNUM.INP 
SUPERNUM.OUT 
2 
7 
1 2 3 7 4 5 6 
5 
1 4 3 2 5 
6 
1 2 3 4 5 6 
5 
1 2 3 4 5 
Lưu ý:Bài tóan này có thể sử dụng Free Pascal để giải quyết . 
Thuật giải : Gọi K,F[I],G[I} lần lượt là độ dài của dãy tăng dài nhất,dãy tăng dài nhất kết thúc tại A[I],dãy tăng dài nhất bắt đầu từ A[I].Như vậy A[I] là một số đặc biệt khi và chỉ khi F[I]+G[I]=K+1.Do đó bài tóan đã được đưa về dạng quy họach động cơ bản thường thấy là tìm dãy con tăng dài nhất.Cách giải thông thường với lọai bài này có độ phức tạp N 2 ,dĩ nhiên không thể áp dụng ở đây do N quá lớn (≤ 10 5 ).Vì vậy ta cần phải hướng tới một thuật giải khác có độ phức tạp nhỏ hơn,ở đây xin giới thiệu với bạn đọc phương pháp tìm dãy con tăng dài nhất với độ phức tạp NlogN,bộ nhớ tỷ lệ với N: 
•  Gọi F[I] là độ dài dãy tăng dài nhất kết thúc tại I,S[I] là giá trị nhỏ nhất trong số các phần tử kết thúc của các dãy tăng có độ dài I. 
•  Tại mỗi thời điểm I:lưu giữ K là độ dài của dãy con tăng dài nhất tới thới điểm đó.Tìm J max sao cho S[J]<A[I] khi đó : 
•  F[I]:=J+1. 
•  Nếu S[F[I]]>A[I] thì S[F[I]]:=A[I]. 
•  Nếu F[I]>K thì K:=F[I]. 
•  Với cách tính như trên dễ thấy tại mỗi thời điểm dãy S là dãy tăng : S[1]<S[2]<.<S[I] (có thể chứng minh bằng quy nạp ).Điều này có nghĩa là mỗi lần tính J ta chỉ phải tốn thời gian tỷ lệ với logN,do đó độ phức tạp của thuật tóan chỉ là NlogN. 
Source Code : Sau đây là chương trình được cài đặt theo tư tưởng ở trên (chạy trên Free Pascal ): 
{ ------------------------------------------------------------ } 
Const input='supernum.inp'; 
output='supernum.out'; 
maxn=10000; 
Var f,g:text; 
n,test,t,l,kmax:longint; 
a,incs,decs,s:array[1..maxn] of longint; 
Function Find(x:longint):longint; 
Var tmax,left,right,mid:longint; 
Begin 
left:=1;right:=kmax;tmax:=0; 
Repeat 
mid:=(left+right) shr 1; 
If s[mid]>a[x] then right:=mid-1 else 
If s[mid]<a[x] then 
Begin 
left:=mid+1; 
tmax:=mid; 
End; 
Until left>right; 
Find:=tmax; 
End; 
Procedure SolveProblem; 
Var i,t,longest,dem:longint; 
Begin 
incs[1]:=1;s[1]:=a[1];kmax:=1;a[1]:=-a[1]; 
For i:=2 to n do 
Begin 
t:=Find(i); 
incs[i]:=t+1; 
If incs[i]>kmax then 
Begin 
kmax:=incs[i]; 
s[kmax]:=a[i]; 
End 
Else If s[incs[i]]>a[i] then s[incs[i]]:=a[i]; 
a[i]:=-a[i]; 
End; 
decs[n]:=1;s[1]:=a[n];kmax:=1; 
longest:=decs[n]+incs[n];dem:=0; 
For i:=n-1 downto 1 do 
Begin 
t:=Find(i); 
decs[i]:=t+1; 
If decs[i]>kmax then 
Begin 
kmax:=decs[i]; 
s[kmax]:=a[i]; 
End 
Else If s[decs[i]]>a[i] then s[decs[i]]:=a[i]; 
If longest<decs[i]+incs[i] then longest:=decs[i]+incs[i]; 
End; 
Fillchar(s,sizeof(s),0); 
For i:=1 to n do 
If (incs[i]+decs[i])=longest then 
Begin 
Inc(dem); 
s[-a[i]]:=1; 
End; 
Writeln(g,dem); 
For i:=1 to n do 
If s[i]=1 then Write(g,i,' '); 
Writeln(g); 
End; 
Begin 
Assign(f,input);Reset(f); 
Assign(g,output);Rewrite(g); 
Readln(f,test); 
For t:=1 to test do 
Begin 
Readln(f,n); 
For l:=1 to n do 
Read(f,a[l]); 
SolveProblem; 
End; 
Close(f);Close(g); 
End.