| 记录编号 |
39357 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
数列 |
最终得分 |
100 |
| 用户昵称 |
 zhangchi |
是否通过 |
通过 |
| 代码语言 |
Pascal |
运行时间 |
0.247 s |
| 提交时间 |
2012-07-09 15:34:41 |
内存使用 |
10.46 MiB |
显示代码纯文本
type node=record a,b,lc,rc,sum,need:int64; end; var n,i,j,newl,newr,tot:longint; ans:int64; a,b,c:array[1..50000] of int64; tree:array[1..200000] of node; procedure maketree(l,r:longint); var t:longint; begin inc(tot); t:=tot; tree[t].a:=l; tree[t].b:=r; if r>l then begin tree[t].lc:=tot+1; maketree(l,(l+r) div 2); tree[t].rc:=tot+1; maketree((l+r) div 2+1,r); end; end; procedure down(x:longint); var l,r:longint; begin l:=tree[x].lc; r:=tree[x].rc; tree[l].sum:=tree[l].sum+tree[x].need*(tree[l].b-tree[l].a+1); tree[l].need:=tree[x].need; tree[r].sum:=tree[r].sum+tree[x].need*(tree[r].b-tree[r].a+1); tree[r].need:=tree[x].need; tree[x].need:=0; end; procedure add(x,value:longint); var l,r,m:longint; begin l:=tree[x].a; r:=tree[x].b; m:=(l+r) div 2; if ((newl<=l)and(r<=newr)) then begin tree[x].sum:=tree[x].sum+value*(r-l+1); tree[x].need:=value; exit; end; if tree[x].need<>0 then down(x); if not((l>newr)or(m<newl)) then add(tree[x].lc,value); if not((m+1>newr)or(r<newl)) then add(tree[x].rc,value); tree[x].sum:=tree[tree[x].lc].sum+tree[tree[x].rc].sum; end; function getsum(x:longint):longint; var l,r,m:longint; temp:int64; begin l:=tree[x].a; r:=tree[x].b; m:=(l+r) div 2; if ((newl<=l)and(r<=newr)) then exit(tree[x].sum); if tree[x].need<>0 then down(x); temp:=0; if not((l>newr)or(m<newl)) then temp:=temp+getsum(tree[x].lc); if not((m+1>newr)or(r<newl)) then temp:=temp+getsum(tree[x].rc); exit(temp); end; begin assign(input,'queueb.in'); reset(input); assign(output,'queueb.out'); rewrite(output); readln(n); for i:=1 to n do readln(a[i]); maketree(0,32767); for i:=1 to n do begin newl:=0; newr:=a[i]-1; if newl<=newr then b[i]:=getsum(1); newl:=a[i]; newr:=a[i]; add(1,1); end; fillchar(tree,sizeof(tree),0); tot:=0; maketree(0,32767); for i:=n downto 1 do begin newl:=0; newr:=a[i]-1; if newl<=newr then c[i]:=getsum(1); newl:=a[i]; newr:=a[i]; add(1,1); end; for i:=1 to n do ans:=ans+b[i]*c[i]; writeln(ans); close(input); close(output); end.