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

Tác giả: RR

Ngôn ngữ: Pascal

uses math;
const
  base=1000000007;

var
  bit,ind,thutu,startof,sl,a,f,last:array[1..100111] of longint;
  val,u,top,i,n:longint;

function find1(val:longint):longint;
    var
      l,r,mid,res:longint;
    begin
      l:=1; r:=top; res:=1;
      while l<=r do
        begin
          mid:=(l+r) shr 1;
          if last[mid]<val then
            begin
              res:=mid;
              l:=mid+1;
            end
          else r:=mid-1;
        end;
      exit(res);
    end;

procedure swap(var a,b:longint);
    var
      tmp:longint;
    begin
      tmp:=a; a:=b; b:=tmp;
    end;

procedure sort(l,r:longint);
    var
      i,j,mf,ma,key:longint;
    begin
      i:=l; j:=r;
      key:=l+random(r-l+1); mf:=f[key]; ma:=a[key];
      repeat
        while (f[i]<mf) or ((f[i]=mf) and (a[i]<ma)) do inc(i);
        while (f[j]>mf) or ((f[j]=mf) and (a[j]>ma)) do dec(j);
        if i<=j then
          begin
            swap(f[i],f[j]);
            swap(a[i],a[j]);
            swap(ind[i],ind[j]);
            inc(i); dec(j);
          end;
      until i>j;
      if i<r then sort(i,r);
      if l<j then sort(l,j);
    end;

function find2(l,r,val:longint):longint;
    var
      res,mid:longint;
    begin
      res:=l;
      while l<=r do
        begin
          mid:=(l+r) shr 1;
          if a[mid]<val then
            begin
              res:=mid;
              l:=mid+1;
            end
          else r:=mid-1;
        end;
      exit(res);
    end;

function get(u:longint):longint;
    var
      tmp,v:longint;
    begin
      if u<=0 then exit(0);
      v:=u-u and (-u);
      tmp:=bit[u]+get(v);
      if tmp>base then dec(tmp,base);
      exit(tmp);
    end;

procedure update(u,k:longint);
    var
      v:longint;
    begin
      bit[u]:=bit[u]+k;
      if bit[u]>base then dec(bit[u],base);
      v:=u+u and (-u);
      if v<=n then update(v,k);
    end;


begin
  read(n);
  for i:=1 to n do read(a[i]);

  last[1]:=a[1]; f[1]:=1; top:=1;
  for i:=2 to n do
    if a[i]<=last[1] then
      begin
        f[i]:=1;
        last[1]:=a[i];
      end
    else if a[i]>last[top] then
      begin
        f[i]:=top+1;
        inc(top); last[top]:=a[i];
      end
    else
      begin
        u:=find1(a[i]);
        f[i]:=u+1;
        last[u+1]:=min(last[u+1],a[i]);
      end;

  for i:=1 to n do ind[i]:=i;

  sort(1,n);
  startof[1]:=1;

  for i:=2 to n do
    if f[i]>f[i-1] then
      startof[f[i]]:=i;

  for i:=1 to n do
    thutu[ind[i]]:=i;

  for i:=1 to n do
    begin
      u:=thutu[i];
      if f[u]=1 then begin sl[u]:=1; update(u,sl[u]); continue; end;

      val:=find2(startof[f[u]-1],startof[f[u]]-1,a[u]);
      sl[u]:=get(val)-get(startof[f[u]-1]-1);
      if sl[u]<0 then inc(sl[u],base);
      update(u,sl[u]);
    end;

  val:=get(n)-get(startof[f[n]]-1);
  if val<0 then inc(val,base);
  writeln(val);
end.

Download