主题:线段树题目(大家来做做)
题目:在数轴上进行一系列操作。每次操作有两种类型,一种是在线段[a,b]上涂上颜色,另一种将[a,b]上的颜色擦去。问经过一系列的操作后,有多少条单位线段[k,k+1]被涂上了颜色。
输入:n
以后n行输入三个整数(n<=1000)。
第一个数为1表示涂色,0表示擦去。
第二、三个数表示线段[a,b](1<=a<b<=2000)。
输出:有多少条单位线段[k,k+1]被涂上了颜色。
数据:
输入:
5
1 1 15
0 4 9
1 7 18
1 7 9
0 1 3
输出:11
程序:
type
aa=record
a,b,l,r,s:integer;
end;
var
i,j,n,a,b,s,t:integer;
tree:array[1..10000] of aa;
procedure maketree(a,b:integer);
var
now:integer;
begin
inc(t); now:=t;
tree[now].a:=a; tree[now].b:=b;
if a+1<b then begin
tree[now].l:=t+1; maketree(a,(a+b) div 2);
tree[now].r:=t+1; maketree((a+b) div 2,b);
end;
end;
procedure ins(a,b,i:integer);
var
k:integer;
begin
if tree[i].s<>1 then
if (tree[i].a=a) and (tree[i].b=b) then tree[i].s:=1
else begin
tree[i].s:=0;
k:=(tree[i].a+tree[i].b) div 2;
if k<=a then ins(a,b,tree[i].r)
else if b<=k then ins(a,b,tree[i].l)
else begin
ins(a,k,tree[i].l);
ins(k,b,tree[i].r);
end;
end;
end;
procedure del(a,b,i:integer);
var
k:integer;
begin
if tree[i].s<>-1 then
if (tree[i].a=a) and (tree[i].b=b) then tree[i].s:=-1
else begin
tree[i].s:=0;
k:=(tree[i].a+tree[i].b) div 2;
if k<=a then del(a,b,tree[i].r)
else if b<=k then del(a,b,tree[i].l)
else begin
del(a,k,tree[i].l);
del(k,b,tree[i].r);
end;
end;
end;
procedure cz(i:integer);
begin
if i<>0 then
if tree[i].s=1 then s:=s+(tree[i].a-tree[i].b)
else if tree[i].s<>-1 then begin
cz(tree[i].l); cz(tree[i].r);
end;
end;
{==============================main===================================}
begin
assign(input,'input.in'); reset(input);
assign(output,'output.out'); rewrite(output);
readln(n);
t:=0; maketree(1,2000);
for i:=1 to n do begin
read(j,a,b);
if j=1 then ins(a,b,1) else del(a,b,1);
end;
cz(1);
writeln(s);
close(input); close(output);
end.
以后还请大家多多指教!
[em2][em2]
输入:n
以后n行输入三个整数(n<=1000)。
第一个数为1表示涂色,0表示擦去。
第二、三个数表示线段[a,b](1<=a<b<=2000)。
输出:有多少条单位线段[k,k+1]被涂上了颜色。
数据:
输入:
5
1 1 15
0 4 9
1 7 18
1 7 9
0 1 3
输出:11
程序:
type
aa=record
a,b,l,r,s:integer;
end;
var
i,j,n,a,b,s,t:integer;
tree:array[1..10000] of aa;
procedure maketree(a,b:integer);
var
now:integer;
begin
inc(t); now:=t;
tree[now].a:=a; tree[now].b:=b;
if a+1<b then begin
tree[now].l:=t+1; maketree(a,(a+b) div 2);
tree[now].r:=t+1; maketree((a+b) div 2,b);
end;
end;
procedure ins(a,b,i:integer);
var
k:integer;
begin
if tree[i].s<>1 then
if (tree[i].a=a) and (tree[i].b=b) then tree[i].s:=1
else begin
tree[i].s:=0;
k:=(tree[i].a+tree[i].b) div 2;
if k<=a then ins(a,b,tree[i].r)
else if b<=k then ins(a,b,tree[i].l)
else begin
ins(a,k,tree[i].l);
ins(k,b,tree[i].r);
end;
end;
end;
procedure del(a,b,i:integer);
var
k:integer;
begin
if tree[i].s<>-1 then
if (tree[i].a=a) and (tree[i].b=b) then tree[i].s:=-1
else begin
tree[i].s:=0;
k:=(tree[i].a+tree[i].b) div 2;
if k<=a then del(a,b,tree[i].r)
else if b<=k then del(a,b,tree[i].l)
else begin
del(a,k,tree[i].l);
del(k,b,tree[i].r);
end;
end;
end;
procedure cz(i:integer);
begin
if i<>0 then
if tree[i].s=1 then s:=s+(tree[i].a-tree[i].b)
else if tree[i].s<>-1 then begin
cz(tree[i].l); cz(tree[i].r);
end;
end;
{==============================main===================================}
begin
assign(input,'input.in'); reset(input);
assign(output,'output.out'); rewrite(output);
readln(n);
t:=0; maketree(1,2000);
for i:=1 to n do begin
read(j,a,b);
if j=1 then ins(a,b,1) else del(a,b,1);
end;
cz(1);
writeln(s);
close(input); close(output);
end.
以后还请大家多多指教!
[em2][em2]