题意/Description:
画一条线一些彩色段,一些预先涂漆段可以由一些后续的覆盖。
你的任务是计算不同的颜色,你终于可以看到段。
读入/Input:
每个数据集的第一行包含正好一个整数n,1 <= N <= 8000,等于着色段的数量。
以下每个n行的由单空格分隔正好3非负整数:
X1 X2 C
x1和x2表示左端点和段的右端点,c表示该段的颜色。
所有数字都在范围[0,8000],和它们都是整数。
输入可能包含几个数据集,处理到文件的末尾。
输出/Output:
输出应包含可从顶部看出,以下这种颜色的片段的计颜色索引的每一行,应根据颜色索引打印。
如果某些颜色不能看到的,你不应该打印出来。
每次打印后的数据集一个空行。
题解/solution:
这题大体和我写的解题报告(PPT1 例2)相同,只是在统计算法上要改一下。Look down!
图,come out. (懒得画树,将就一下)
用ls表示上一个颜色,如果当前颜色与ls不同,那给这个颜色加一。例:
ls颜色为空,而一区间为红,红加一,ls=红。
ls颜色为红,而三区间为蓝,蓝加一,ls=蓝。
以此类推......
代码/Code:
type
arr=record
l,r:longint;
color:longint;
end;
var
tree:array [0..32001] of arr;
ans:array [0..8001] of longint;
n,m,ls,max_co:longint;
procedure cre(p,b,e:longint);
var
m:longint;
begin
with tree[p] do
begin
l:=b; r:=e; color:=-1;
if e-b=1 then exit;
m:=(b+e) div 2;
cre(p*2,b,m);
cre(p*2+1,m,e);
end;
end;
procedure ins(p,a,b,c:longint);
var
m:longint;
begin
with tree[p] do
begin
if color<>c then
begin
m:=(l+r) div 2;
if (a=l) and (b=r) then color:=c else
begin
if color>=0 then
begin
tree[p*2].color:=color;
tree[p*2+1].color:=color;
end;
color:=-2;
if b<=m then ins(p*2,a,b,c) else
if a>=m then ins(p*2+1,a,b,c) else
begin
ins(p*2,a,m,c);
ins(p*2+1,m,b,c);
end;
end;
end;
end;
end;
procedure count(p:longint);
begin
with tree[p] do
begin
if color>=0 then
begin
if color<>ls then
begin
inc(ans[color]);
ls:=color;
end;
exit;
end;
if color=-1 then
begin
ls:=color;
exit;
end;
count(p*2);
count(p*2+1);
end;
end;
procedure main;
var
i,x,y,z:longint;
begin
m:=8000;
while not eof do
begin
fillchar(ans,sizeof(ans),0);
readln(n);
ls:=-1; max_co:=-(maxlongint div 3);
cre(1,0,m);
for i:=1 to n do
begin
readln(x,y,z);
ins(1,x,y,z);
if z>max_co then max_co:=z;
end;
count(1);
for i:=0 to max_co do
if ans[i]>0 then
writeln(i,' ',ans[i]);
writeln;
end;
end;
begin
main;
end.