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.