CVJETICI - Cvjetici

Tác giả: flashmt

Ngôn ngữ: Pascal

uses math;
var n,nn,i,x,y,c,d:longint;
    a:array[1..400000] of longint;
    b:array[1..100000,0..1] of longint;

function calc(node,l,r,x:longint):longint;
var mid,res:longint;
begin
     res:=0;
     if (l=x) and (r=x) then res:=a[node]
     else
     begin
          mid:=(l+r) shr 1;
          if x<=mid then res:=calc(node shl 1,l,mid,x)+a[node]
          else res:=calc(node shl 1+1,mid+1,r,x)+a[node];
     end;
     calc:=res;
end;


procedure add(node,l,r,x,y:longint);
var mid:longint;
begin
     if (l=x) and (r=y) then a[node]:=a[node]+1
     else
     begin
          mid:=(l+r) shr 1;
          if x<=mid then add(node shl 1,l,mid,x,min(y,mid));
          if y>mid then add(node shl 1+1,mid+1,r,max(x,mid+1),y);
     end;
end;

procedure minus(node,l,r,x,val:longint);
var mid:longint;
begin
     if (l=x) and (r=x) then a[node]:=a[node]-val
     else
     begin
          mid:=(l+r) shr 1;
          if x<=mid then minus(node shl 1,l,mid,x,val)
          else minus(node shl 1+1,mid+1,r,x,val);
     end;
end;

begin
     read(nn);
     n:=0;
     for i:=1 to nn do
     begin
          read(b[i,0],b[i,1]);
          n:=max(n,b[i,1]);
     end;
     for i:=1 to nn do
     begin
          x:=b[i,0]; y:=b[i,1];
          c:=calc(1,1,n,x);
          d:=calc(1,1,n,y);
          minus(1,1,n,x,c);
          minus(1,1,n,y,d);
          writeln(c+d);
          if x<y-1 then add(1,1,n,x+1,y-1);
     end;
end.

Download