Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:树状数组,O(N*logN*logN) 的复杂度 水过,可以在直接在树状数组上二分降低一个logN

Posted by xyyxiao07 at 2013-04-19 13:35:01 on Problem 2892
In 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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator