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]•  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]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]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:=