如果你AC了 这组数据必然过不了
1
3
1 10
1 3
6 10

正确是3 但是只当你算出来是2的时候你才能A
为什么呢
因为4-5这段区间离散化的时候并没有处理到

下面是最后的AC程序 加上大括号部分代码之后才是正确程序







== Code ==





program poj2528;
var
 c:array[0..80000] of longint;
 v:array[0..30000] of longint;
 o:array[0..30000] of boolean ;
 a,b:array[1..10000] of longint;
 t,tt,n,i,x,cnt,ans:longint;

procedure qsort(l,r:longint) ;
var
 i,j,t,x:longint;
begin
 i := l;
 j := r;
 x := v[(l+r) shr 1] ;
 repeat
  while v[i] < x do inc(i) ;
  while v[j] > x do dec(j) ;
  if i <= j then
   begin
    t := v[i] ;
    v[i] := v[j] ;
    v[j] := t ;
    inc(i) ;
    dec(j) ;
   end;
 until i > j ;
 if i < r then qsort(i,r) ;
 if l < j then qsort(l,j) ;
end;

procedure pushdown(x:longint);
begin
 if c[x] <> 0 then
  begin
   c[x shl 1] := c[x] ;
   c[x shl 1+1] := c[x] ;
   c[x] := 0 ;
  end;
end;

procedure modify(ll,rr,u,l,r,x:longint) ;
var
 m:longint;
begin
 if (ll <= l) and (r <= rr) then
  begin
   c[x] := u ;
   exit ;
  end;
 pushdown(x) ;
 m := (l+r) shr 1;
 if ll <= m then modify(ll,rr,u,l,m,x shl 1) ;
 if m < rr then modify(ll,rr,u,m+1,r,x shl 1+1) ;
end;

function query(l,r,x:longint):longint;
var
 m:longint;
begin
 if l > r then exit;
 if c[x] <> 0 then
  begin
   if not o[c[x]] then
    begin
     o[c[x]] := true ;
     inc(ans) ;
    end ;
   exit;
  end;
 if l = r then exit ;
 m := (l+r) shr 1;
 query(l,m,x shl 1);
 query(m+1,r,x shl 1+1);
end;

function seek(x:longint):longint;
var
 l,r,m:longint;
begin
 l := 1;
 r := cnt ;
 while l <= r do
  begin
   m := (l+r) shr 1 ;
   if v[m] = x then exit(m) else
   if v[m] < x then
    l := m+1 else
    r := m-1 ;
  end ;
 exit(l) ;
end;

BEGIN
 read(t) ;
 for tt := 1 to t do
  begin
   fillchar(c,sizeof(c),0) ;
   read(n) ;
   fillchar(v,sizeof(v),0);
   cnt := 0 ;
   for i := 1 to n do
    begin
     read(a[i],b[i]) ;
     inc(cnt) ;
     v[cnt] := a[i] ;
     inc(cnt) ;
     v[cnt] := b[i] ;
    end;
   qsort(1,cnt) ;
   x := 0 ;
   for i := 1 to cnt do
    if v[i] <> v[i-1] then
     begin
      inc(x) ;
      v[x] := v[i] ;
     end;
   cnt := x ;                      {
   for i := 2 to cnt do
    if v[i]-v[i-1] > 1 then
     begin
      inc(x) ;
      v[x] := v[i-1]+1;
     end;
   cnt := x ;                     }
   qsort(1,cnt);
   for i := 1 to n do
    modify(seek(a[i]),seek(b[i]),i,1,cnt,1) ;
   fillchar(o,sizeof(o),false) ;
   ans := 0 ;
   query(1,cnt,1) ;
   writeln(ans) ;
  end;
END.

• 你的数据过了,而且我也AC了 (0) comzyh 2013-04-19 11:35:01
• haha , 我也过了这个数据， 也ac了 (2878) rush_again 2013-05-24 10:39:37
• Re:表示POJ数据是错的 不处理特殊情况 内附反例数据和代码 (14) lx865712528 2013-07-24 17:44:15
  • Re:表示POJ数据是错的 不处理特殊情况 内附反例数据和代码 (5) z20c12h 2017-07-17 17:35:00