NTSEQ - Số lượng dãy con tăng
Tác giả: ladpro98
Ngôn ngữ: Pascal
program NTSEQ;
const
MAXN = 100005;
MODULO = 1000000007;
type
TPair = record
value, count: longint;
end;
arrayN = array[0..MAXN] of longint;
dynamicArray = array of TPair;
var
a, F: arrayN;
size: arrayN;
H: array[0..MAXN] of dynamicArray;
n, LIS: longint;
procedure normalize(var a: longint);
begin
if (a < 0) then inc(a, MODULO);
if (a >= MODULO) then dec(a, MODULO);
end;
procedure initialize();
var i, L, R, mid: longint;
minA: array[0..MAXN] of longint;
begin
minA[0] := -maxLongint; LIS := 0;
for i := 1 to n do
begin
L := 0; R := LIS;
while (L <= R) do
begin
mid := (L + R) div 2;
if (minA[mid] < a[i]) then
begin
F[i] := mid + 1;
L := mid + 1;
end
else begin
R := mid - 1;
end;
end;
minA[F[i]] := a[i];
inc(size[F[i]]);
if (LIS < F[i]) then LIS := F[i];
end;
// writeln(LIS);
end;
procedure solve();
var i, L, R, mid, first: longint;
idx: arrayN;
begin
// for i := 1 to n do writeln('F ', i, ' ', F[i]);
// for i := 1 to LIS do writeln('size ', i, ' ', size[i]);
for i := 1 to LIS do
begin
setLength(H[i], size[i] + 2);
H[i][0].count := 0;
end;
for i := 1 to LIS do size[i] := 0;
for i := 1 to n do
begin
inc(size[F[i]]);
H[F[i]][size[F[i]]].value := a[i];
H[F[i]][size[F[i]]].count := 0;
idx[i] := size[F[i]];
end;
for i := 1 to LIS do size[i] := 0;
for i := 1 to n do
begin
if (F[i] = 1) then
begin
inc(size[1]);
H[1][idx[i]].count := H[1][idx[i] - 1].count + 1;
normalize(H[1][idx[i]].count);
continue;
end;
L := 1; R := size[F[i] - 1];
while (L <= R) do
begin
mid := (L + R) div 2;
if (H[F[i] - 1][mid].value < a[i]) then
begin
first := mid;
R := mid - 1;
end
else begin
L := mid + 1;
end;
end;
inc(size[F[i]]);
H[F[i]][idx[i]].count := H[F[i]][idx[i] - 1].count + H[F[i] - 1][size[F[i] - 1]].count - H[F[i] - 1][first - 1].count;
normalize(H[F[i]][idx[i]].count);
end;
writeln(H[LIS][size[LIS]].count);
end;
procedure main();
var i: longint;
begin
// assign(input, 'NTSEQ.inp'); reset(input);
read(n);
for i := 1 to n do read(a[i]);
inc(n); a[n] := maxLongint;
initialize();
solve();
end;
begin
main();
end.