FOCUS - Chuyên gia ruồi

Tác giả: flashmt

Ngôn ngữ: Pascal

const fi='';
      maxn=400040;
var n,num,max:longint;
    aa,d,f:array[0..maxn] of longint;
    a:array[0..maxn shr 1] of longint;
    b:array[0..maxn shr 1,1..3] of longint;

procedure sort(l,r:longint);
var i,j,x,y:longint;
begin
     i:=l; j:=r; x:=aa[(i+j) shr 1];
     repeat
           while aa[i]<x do i:=i+1;
           while aa[j]>x do j:=j-1;
           if i<=j then
           begin
                y:=aa[i]; aa[i]:=aa[j]; aa[j]:=y;
                y:=d[i]; d[i]:=d[j]; d[j]:=y;
                i:=i+1; j:=j-1;
           end;
     until i>j;
     if i<r then sort(i,r);
     if l<j then sort(l,j);
end;

procedure rf;
var i,j:longint; c:char;
begin
     readln(n);
     for i:=1 to n do
     begin
          read(c);
          if c<>'?' then
          begin
               readln(a[i]);
               num:=num+1;
               aa[num]:=a[i];
               d[num]:=i;
               if c='-' then a[i]:=-a[i];
          end
          else
          begin
               for j:=1 to 3 do read(b[i,j]);
               num:=num+2;
               aa[num-1]:=b[i,2]; d[num-1]:=-i;
               aa[num]:=b[i,3]; d[num]:=i;
               readln;
          end;
     end;
end;

procedure edit;
var i:longint;
begin
     max:=0;
     for i:=1 to num do
     begin
          if aa[i]<>aa[max] then
          begin
               inc(max);
               aa[max]:=aa[i];
          end;
          if a[abs(d[i])]<>0 then
          begin
               if a[d[i]]>0 then a[d[i]]:=max
               else a[d[i]]:=-max;
          end
          else
          begin
               if d[i]<0 then b[-d[i],2]:=max
               else b[d[i],3]:=max;
          end;
     end;
end;

procedure add(x,v:longint);
begin
     while x<=max do
     begin
          f[x]:=f[x]+v;
          x:=x+x and (-x);
     end;
end;

function calc(x:longint):longint;
var r:longint;
begin
     r:=0;
     while x>0 do
     begin
          r:=r+f[x];
          x:=x-x and (-x);
     end;
     calc:=r;
end;

procedure pr;
var i,t,l,r,m,u,j:longint;
begin
     sort(1,num);
     edit;
     for i:=1 to n do
         if a[i]<>0 then
         begin
              if a[i]>0 then add(a[i],1)
              else add(-a[i],-1);
         end
         else
         begin
            t:=calc(b[i,2]-1)+b[i,1];
            l:=b[i,2]; r:=b[i,3];
            if calc(r)<t then writeln(0)
            else
            begin
               while l<=r do
               begin
                    m:=(l+r) shr 1;
                    u:=calc(m);
                    if u<t then l:=m+1
                    else r:=m-1;
               end;
               for j:=m-1 to m+1 do
                   if (j>=b[i,2]) and (j<=b[i,3]) and (calc(j)>=t) then break;
               writeln(aa[j]);
            end;
         end;
end;

begin
     assign(input,fi); reset(input);
     rf;
     pr;
     close(input);
end.

Download