1660: [Usaco2006 Nov]Bad Hair Day 乱发节

Time Limit: 2 Sec  Memory Limit: 64 MB

Submit: 665  Solved: 318

[][]

Description

 

Input

* Line 1: 牛的数量 N。

 * Lines 2..N+1: 第 i+1 是一个整数，表示第i头牛的高度。

Output

* Line 1: 一个整数表示c[1] 至 c[N]的和。

Sample Input

6

10

3

7

4

12

2

输入解释:

六头牛排成一排，高度依次是 10, 3, 7, 4, 12, 2。

Sample Output

5

3+0+1+0+1=5

HINT

Source

题解：其实可以用单调队列稍微改一下的单调堆做。可是傲娇的我偏不，嗯哼——建立一棵线段树树，在初始化之后只要支持一种萌萌哒功能就够了：在区间内查找位置最靠左的大于或等于某值的点的位置，比如样例，则cash(1,n,1,2,n,10)得到的就是5，然后萌萌哒线段树树就这么萌萌哒Accept了（本以为会小小的TLE一下的，可一遍下来居然WA，再一看居然是数组开小了TT，最终出乎本萌妹意料的——604ms不解释）

 

1 var 2    i,k,m,n:longint; 3    l,j:int64; 4    a,b,c:array[0..500000] of longint; 5 function min(x,y:longint):longint; 6          begin 7               if x
     
      y then max:=x else max:=y;12          end;13 procedure built(x,y,z:longint);14           begin15                if x=y then16                   begin17                        a[z]:=c[x];18                        b[z]:=x;19                        exit;20                   end;21                built(x,(x+y) div 2,z*2);22                built((x+y) div 2+1,y,z*2+1);23                a[z]:=max(a[z*2],a[z*2+1]);24                if a[z]=a[z*2] then b[z]:=b[z*2] else b[z]:=b[z*2+1];25           end;26 function cash(x,y,z,l,r,t:longint):int64;27          var28             i,j,k:longint;29          begin30               if l>r then exit(-1);31               if a[z]
      
       =t) then exit(l);33               if (l=r) or (x=y) then exit(-1);34               i:=cash(x,(x+y) div 2,z*2,l,min((x+y) div 2,r),t);35               if i=-1 then36                  cash:=cash((x+y) div 2+1,y,z*2+1,max((x+y) div 2+1,l),r,t)37               else38                   cash:=i;39          end;40 begin41      readln(n);42      for i:=1 to n do43          readln(c[i]);44      built(1,n,1);45      l:=0;46      for i:=1 to n-1 do47          begin48               j:=(cash(1,n,1,i+1,n,c[i]));49               if j=-1 then l:=l+int64(int64(n)-int64(i)) else l:=l+int64((int64(j)-int64(i))-1);50          end;51      writeln(l);52 end.