Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:树状数组,O(N*logN*logN) 的复杂度 水过,可以在直接在树状数组上二分降低一个logNIn Reply To:树状数组,O(N*logN*logN) 的复杂度 水过,可以在直接在树状数组上二分降低一个logN Posted by:WilliamACM at 2013-01-25 14:56:41 能帮忙看看哪里错了吗? var a,r:array[0..50001]of longint; t,n,m,i,j,k,max,min,mid:longint; c:char; function lb(n:longint):longint; begin exit(n and -n); end; procedure ins(k:longint); begin repeat a[k]:=a[k]+1; k:=k+lb(k); until k>n; end; procedure del(k:longint); begin repeat a[k]:=a[k]-1; k:=k+lb(k); until k>n; end; function se(k:longint):longint; begin se:=0; repeat se:=se+a[k]; k:=k-lb(k); until k<=0; end; function che(k:longint):longint; var t:longint; begin if se(k)-se(k-1)=1 then exit(0); k:=se(k)+1; min:=0; max:=n; repeat mid:=(min+max) div 2; t:=se(mid); if t>k then max:=mid-1 else if t=k then max:=mid else min:=mid; until min+1=max; che:=max; min:=0; max:=n; k:=k-1; repeat mid:=(min+max) div 2; t:=se(mid); if t>k then max:=mid-1 else if t=k then max:=mid else min:=mid; until min+1=max; che:=che-max-1; end; begin readln(n,m); n:=n+1; ins(n); t:=0; for i:=1 to m do begin read(c); if c='D' then begin readln(c,k); ins(k); inc(t); r[t]:=k; end; if c='Q' then begin readln(c,k); writeln(che(k)); end; if c='R' then begin readln; del(r[t]); dec(t); end; end; end. Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator