亂頭發節(badhair）

題意/Description:

       農民John的某 N 頭奶牛 (1 <= N <= 80,000) 正在過亂頭發節！由于每頭牛都意識到自己淩亂不堪的發型，FJ 希望統計出能夠看到其他牛的頭發的牛的數量。 　　每一頭牛 i有一個高度 h[i] (1 <= h[i] <= 1,000,000,000)而且面向東方排成一排(在我們的圖中是向右)。是以，第i頭牛可以看到她前面的那些牛的頭，（即i+1, i+2,等等），隻要那些牛的高度嚴格小于她的高度。

       每一頭牛 i有一個高度 h[i] (1 <= h[i] <= 1,000,000,000)而且面向東方排成一排(在我們的圖中是向右)。是以，第i頭牛可以看到她前面的那些牛的頭，（即i+1, i+2,等等），隻要那些牛的高度嚴格小于她的高度。

例如這個例子:

              = =           = =           = =    -      =           牛面向右側 --> =    =     = = -  = = = = = = = = = 1  2 3  4  5 6

       牛#1 可以看到她們的發型 #2, 3, 4

       牛#2 不能看到任何牛的發型

       牛#3 可以看到她的發型 #4

       牛#4 不能看到任何牛的發型

       牛#5 可以看到她的發型 6

       牛#6 不能看到任何牛的發型!

       讓 c[i] 表示第i頭牛可以看到發型的牛的數量；請輸出 c[1] 至 c[N]的和。如上面的這個例子，正确解是3 + 0 + 1 + 0 + 1 + 0 = 5。

讀入/Input：

       Line 1: 牛的數量 N。

       Lines 2..N+1: 第 i+1 是一個整數，表示第i頭牛的高度。

輸出/Output：

       Line 1: 一個整數表示c[1] 至 c[N]的和。

題解/solution：

       定義一個數組num，num[i]是第一至第i牛比我高的右側。這是很明顯的，在計算num[i]對所有i等同于解決問題。

       一個簡單的現象是，如果a[i]>a[j]，num[i]>j時，num[i]>=num[j]。如果num[i]a[i]>a[j]，則與num[j]的定義沖突。那麼num[i]開始作為i+1的和，在a[num[i]]<a[i]中，用num[i]代替num[num[i]]。

       時間複雜度O(n)，怎麼證明我不會。

代碼/Code：

var
  n:longint;
  a,num:array [0..80001] of longint;
  ans:int64;
procedure init;
var
  i:longint;
begin
  fillchar(a,sizeof(a),$7f);
  readln(n);
  for i:=1 to n do
    readln(a[i]);
  ans:=0;
end;

procedure main;
var
  i,t:longint;
begin
  for i:=n downto 1 do
    begin
      t:=0; num[i]:=i+1;
      while (num[i]<=n) and (a[num[i]]<a[i]) do
        begin
          t:=t+num[num[i]]-num[i];
          num[i]:=num[num[i]];
        end;
      ans:=ans+t;
    end;
end;

begin
  init;
  main;
  write(ans);
end.