## Editorial for Chia dãy

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

#### Code mẫu của flashmt

const fi='';
var test,it,n,re:longint;
b,f:array[1..100000] of longint;

procedure rf;
var i:longint;
begin
for i:=1 to n do read(b[i]);
end;

function bs(x:longint):longint;
var l,r,m,i:longint;
begin
l:=1; r:=re;
while l<=r do
begin
m:=(l+r) shr 1;
if f[m]<=x then r:=m-1
else l:=m+1;
end;
for i:=m-1 to m+1 do
if (i>0) and (i<=re) and (f[i]<=x) then exit(i);
end;

procedure pr;
var i,x:longint;
begin
re:=1; f[1]:=b[1];
for i:=2 to n do
if b[i]<f[re] then
begin
re:=re+1; f[re]:=b[i];
end
else
begin
x:=bs(b[i]);
f[x]:=b[i];
end;
writeln(re);
end;

begin
assign(input,fi); reset(input);
rf;
pr;
close(input);
end.


program qbdivseq;
uses    math;
const   fi='';
maxN=100005;
var     a,f:array[1..maxN] of longint;
n,d:longint;

procedure input;
var     f:text;
i:longint;
begin
assign(f,fi);
reset(f);
for i:=1 to n do
close(f);
end;

function find(r,key:longint):longint;
var     l,m,k:longint;
begin
l:=1;
while l<=r do
begin
m:=(l+r) shr 1;
if f[m]<=key then
begin
k:=m;
r:=m-1;
end
else
l:=m+1;
end;
exit(k);
end;

procedure process;
var     i:longint;
begin
d:=1;
for i:=1 to n do
if a[i]<f[d] then
begin
inc(d);
f[d]:=a[i];
end
else
f[find(d,a[i])]:=a[i];

end;

begin
input;
process;
write(d);
end.


{$R+,Q+} const FINP=''; FOUT=''; MAXN=100001; var a,b:array[1..MAXN] of longint; k,n:longint; f1,f2:text; procedure openF; inline; begin assign(f1,FINP); reset(f1); assign(f2,FOUT); rewrite(f2); end; procedure closeF; inline; begin close(f1); close(f2); end; procedure inp; inline; var i:longint; begin read(f1,n); for i:=1 to n do read(f1,a[i]); end; procedure ans; inline; begin writeln(f2,k); end; var mid,gt:longint; function find(l,r:longint):longint; inline; begin if (b[l]<=gt) and (b[l-1]>gt) then exit(l); if (b[r]<=gt) and (b[r-1]>gt) then exit(r); mid:=(l+r)>>1; if (b[mid]<=gt) and (b[mid-1]>gt) then exit(mid) else if b[mid]<=gt then exit(find(l,mid-1)) else exit(find(mid+1,r)); end; procedure solve; var i,j:longint; begin k:=1; b[1]:=a[1]; for i:=2 to n do begin if a[i]<b[k] then begin inc(k); b[k]:=a[i]; end else if a[i]>=b[1] then b[1]:=a[i] else begin gt:=a[i]; j:=find(2,k); b[j]:=a[i]; end; end; end; begin openF; inp; solve; ans; closeF; end.  #### Code mẫu của hieult #include <stdio.h> //#include <conio.h> int main() { int n,f[100001],a[100001],t; scanf("%d",&n); for(int i = 1;i<=n;i++) scanf("%d",&a[i]); t = 1; f[1] = a[1]; for(int i = 2;i<=n;i++) { if(a[i]<f[t]) { t++; f[t] = a[i]; } else if(a[i]>=f[1]) f[1] = a[i]; else { int u = 1,v = t,r; while(v-u>1) { r = (u+v)/2; if(a[i]<f[r]) u = r; else v = r; } f[v] = a[i]; } } printf("%d",t); //getch(); }  #### Code mẫu của ll931110 {$MODE DELPHI}
Program QBDIVSEQ;
Const
input  = '';
output = '';
maxn = 100000;
Var
a,s: array[1..maxn] of integer;
n,k: integer;

Procedure init;
Var
f: text;
i: integer;
Begin
Assign(f, input);
Reset(f);

For i:= 1 to n do readln(f, a[i]);

Close(f);
End;

Procedure update(i: integer);
Var
inf,sup,med,r: integer;
Begin
If s[k] > a[i] then
Begin
inc(k);
s[k]:= a[i];
exit;
End;

inf:= 1;
sup:= k;

r:= 0;
Repeat
med:= (inf + sup) div 2;
If s[med] = a[i] then exit;
If s[med] > a[i] then inf:= med + 1 else
Begin
r:= med;
sup:= med - 1;
End;
Until inf > sup;

s[r]:= a[i];
End;

Procedure optimize;
Var
i: integer;
Begin
k:= 1;
s[1]:= a[1];
For i:= 2 to n do update(i);
End;

Procedure printresult;
Var
f: text;
Begin
Assign(f, output);
Rewrite(f);
Writeln(f, k);
Close(f);
End;

Begin
init;
optimize;
printresult;
End.


#### Code mẫu của khuc_tuan

#include <iostream>
#include <vector>
using namespace std;

int main() {
int n;
scanf("%d", &n);
vector<int> v;
for(int i=0;i<n;++i) {
int x;
scanf("%d", &x);
vector<int> :: iterator p = lower_bound(v.begin(), v.end(), x, greater<int>());
if(p==v.end()) v.push_back(x);
else *p = x;
}
cout << v.size() << endl;
return 0;
}