type
  auu=record
    l,r,g:longint;
  end;
var
  f:array[1..200000] of longint;
  s:array[1..2000000] of auu;
  i,j,n,t,d,ans,c,i1:longint;
  a1,a2:array[1..100000] of longint;
  check:array[1..100000] of boolean;
procedure paixu(l,r:longint);
var
  i,j,t,li,lj:longint;
begin
  i:=l; j:=r;
  t:=(i+j)div 2;
  repeat
    while (a1[i]<=a1[t]) and (i<t) do inc(i);
    while (a1[j]>=a1[t]) and (j>t) do dec(j);
    li:=a2[i]; lj:=a2[j];
    d:=a1[i]; a1[i]:=a1[j]; a1[j]:=d;

    f[li]:=j; f[lj]:=i;
    a2[i]:=lj; a2[j]:=li;
    if i=t then t:=j else if t=j then t:=i;
  until i=j;
  if i-1>l then paixu(l,i-1);
  if j+1<r then paixu(i+1,r);
end;
procedure lishanhua;
var
  i,sc,lin:longint;
begin
  sc:=a1[i];
  a1[i]:=1;
  for i:=2 to n*2 do
  begin
    if a1[i]=sc then a1[i]:=a1[i-1] else
    begin
      lin:=a1[i];
      if a1[i]-sc=1 then a1[i]:=a1[i-1]+1 else
      a1[i]:=a1[i-1]+2;
      sc:=lin;
    end;
  end;
end;
procedure chuli(se,l,r,v:longint);
var
  i,j,mid:longint;
begin
  if s[v].g<>0 then exit;
  mid:=(s[v].l+s[v].r) div 2;
  if (s[v].l=l) and (s[v].r=r) then
  begin
    s[v].g:=se;
    exit;
  end;
  if (r<=mid) then
  begin
    chuli(se,l,r,v*2);
    if (s[v*2].g<>0) and (s[v*2+1].g<>0) then
    s[v].g:=-1;
    exit;
  end;
  if (l>mid) then
  begin
    chuli(se,l,r,v*2+1);
    if (s[v*2].g<>0) and (s[v*2+1].g<>0) then
    s[v].g:=-1;
    exit;
  end;
  chuli(se,l,mid,v*2);
  chuli(se,mid+1,r,v*2+1);
  if (s[v*2].g<>0) and (s[v*2+1].g<>0) then
    s[v].g:=-1;
end;
procedure jianshu(v,l,r:longint);
begin
  s[v].l:=l; s[v].r:=r;
  if l=r then exit;
  jianshu(v*2,l,(l+r)div 2);
  jianshu(v*2+1,(l+r)div 2+1,r);
end;
procedure shaomiao(v:longint);
begin
  if (s[v].g<>0) and (s[v].g<>-1) then
  begin
    if check[s[v].g]=false then inc(ans);
    check[s[v].g]:=true;
    if s[v].l=s[v].r then exit;
    shaomiao(v*2);
    shaomiao(v*2+1);
    exit;
  end;
  if s[v].l=s[v].r then exit;
  if (s[v].g=0) or (s[v].g=-1) then
  begin
    shaomiao(v*2);
    shaomiao(v*2+1);
  end;
end;
begin
readln(c);
for i1:=1 to c do
begin
  ans:=0;
  fillchar(s,sizeof(s),0);
  fillchar(check,sizeof(check),false);
  readln(n);
  for i:=1 to n do
  begin
    readln(a1[i*2-1],a1[i*2]);
    a2[i*2-1]:=i; a2[2*i]:=i+n;
    f[i]:=i*2-1; f[i+n]:=i*2;
  end;
  paixu(1,n*2);
  lishanhua;
  jianshu(1,1,a1[n*2]);

  for i:=n downto 1 do
  begin

    chuli(i,a1[f[i]],a1[f[i+n]],1);
  end;
  shaomiao(1);
  writeln(ans);
end;
end.

• Re:哪未大牛有测试数据啊，怎么我的老是wa!1 (39) 305636397 2010-03-09 18:50:01
  • Re:哪未大牛有测试数据啊，怎么我的老是wa!1 (43) Gray236 2010-08-04 22:09:32