POJ 2528（数据有误的线段树）

此题数据有误……

是我英文太差，还是答案出错……

Program P2528;
const
maxn=10000;
maxr=10000000;
var
t,n,i,j,k:longint;
a,b,v:array[1..maxn*2] of longint;
h:array[1..maxr] of longint;
col:array[1..maxn*100] of longint;
visit:array[1..maxn*2] of boolean;
procedure qsort(l,r:longint);
var
i,j,m,p:longint;
begin
i:=l;
j:=r;
m:=v[(l+r) div 2];
repeat
while v[i]<m do inc(i);
while v[j]>m do dec(j);
if i<=j then
begin
p:=v[i];
v[i]:=v[j];
v[j]:=p;
inc(i);
dec(j);
end;
until i>j;
if l<j then qsort(l,j);
if i<r then qsort(i,r);
end;
procedure update(l,r,sonl,sonr,root,color:longint);
var
i,j,k,mid:longint;
begin
mid:=(l+r) shr 1;
if (sonl<=l) and (r<=sonr) then
begin
col[root]:=color;
exit;
end;
if (col[root]>=0) then
begin
col[root*2]:=col[root];
col[root*2+1]:=col[root];
col[root]:=-1;
end;
if not((mid<sonl) or (sonr<l)) then update(l,mid,sonl,sonr,root*2,color);
if not((r<sonl) or (sonr<mid+1)) then update(mid+1,r,sonl,sonr,root*2+1,color);
end;
function dfs(l,r,root:longint):longint;
var
i,j,mid:longint;
begin
mid:=(l+r) shr 1;
if col[root]=0 then exit(0);
if col[root]>0 then
begin
if not(visit[col[root]]) then
begin
visit[col[root]]:=true;
exit(1);
end
else exit(0);
end;
exit(dfs(l,mid,root*2)+dfs(mid+1,r,root*2+1));
end;
begin
read(t);
while t>0 do
begin
dec(t);
read(n);
for i:=1 to n do
begin
read(a[i],b[i]);
v[i]:=a[i];
v[n+i]:=b[i];
end;
qsort(1,2*n);
j:=1;
for i:=2 to 2*n do
if v[i]<>v[i-1] then
begin
inc(j);
v[j]:=v[i];
end;
for i:=1 to j do h[v[i]]:=i;
fillchar(col,sizeof(col),0);
for i:=1 to n do
begin
update(1,j,h[a[i]],h[b[i]],1,i);
end;
fillchar(visit,sizeof(visit),false);
writeln(dfs(1,j,1));
end;
end.

最后

以上就是友好枫叶为你收集整理的POJ 2528（数据有误的线段树）的全部内容，希望文章能够帮你解决POJ 2528（数据有误的线段树）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。