| ||||||||||
| 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