NTSEQ - Số lượng dãy con tăng

Tác giả: flashmt

Ngôn ngữ: Pascal

const fi='';
      maxn=100010;
      z=1000000007;
var n,maxc,re,res:longint;
    f,a,d,e,g:array[1..maxn] of longint;

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

procedure sort(l,r:longint);
var i,j,x,y:longint;
begin
     i:=l; j:=r; x:=a[(i+j) shr 1];
     repeat
           while a[i]<x do i:=i+1;
           while a[j]>x do j:=j-1;
           if i<=j then
           begin
                y:=a[i]; a[i]:=a[j]; a[j]:=y;
                y:=d[i]; d[i]:=d[j]; d[j]:=y;
                i:=i+1; j:=j-1;
           end;
     until i>j;
     if i<r then sort(i,r);
     if l<j then sort(l,j);
end;

procedure edit;
var i:longint;
begin
     maxc:=1; e[d[1]]:=1;
     for i:=2 to n do
     begin
          if a[i]<>a[maxc] then
          begin
               maxc:=maxc+1;
               a[maxc]:=a[i];
          end;
          e[d[i]]:=maxc;
     end;
end;

procedure add(x,val:longint);
begin
     while x<=maxc do
     begin
          if val<f[x] then f[x]:=val
          else exit;
          x:=x+x and (-x);
     end;
end;

function calc(x:longint;var val:longint):longint;
var r:longint;
begin
     r:=0; val:=0;
     while x>0 do
     begin
          if f[x]=r then
          begin
               val:=val+g[x];
               if val>=z then val:=val-z;
          end;
          if f[x]>r then
          begin
               r:=f[x];
               val:=g[x];
          end;
          x:=x-x and (-x);
     end;
     calc:=r;
end;

procedure update(x,t,u:longint);
begin
     while x<=maxc do
     begin
          if t<f[x] then exit;
          if t=f[x] then
          begin
               g[x]:=g[x]+u;
               if g[x]>=z then g[x]:=g[x]-z;
          end;
          if t>f[x] then
          begin
               g[x]:=u;
               f[x]:=t;
          end;
          x:=x+x and (-x);
     end;
end;

procedure pr;
var i,t,u:longint;
begin
     sort(1,n);
     edit;
     re:=0; res:=0;
     for i:=1 to n do
     begin
          t:=calc(e[i]-1,u);
          if u=0 then u:=1;
          update(e[i],t+1,u);
     end;
     re:=calc(maxc,res);
     writeln(res);
end;

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

Download