回 帖 发 新 帖 刷新版面

主题:线段树题目(大家来做做)

题目:在数轴上进行一系列操作。每次操作有两种类型,一种是在线段[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]

回复列表 (共8个回复)

沙发

大家怎么不做呀?

板凳

大家来给我提提意见吧.

3 楼

'经过一系列的操作后'一系列的操作是如何操作???
我其实没怎么看懂题~

4 楼

del(a,b)
ins(a,b)

里面最好加上判断 [a,b] 是否在 [ tree[i].a , tree[i].b ] 的范围中。

5 楼

年轻好。。思路活跃。。但是您也用不着这么麻烦啊。。
还是我没看懂题意。。

program tuse;
var n,i,j,sum,f,left,right:integer;
    a:array[1..2000] of 0..1;
begin
assign(input,'input.in');
assign(output,'output.out');
reset(input);
rewrite(output);
readln(n);
for i:=1 to n do
     begin
      read(f,left,right);readln;
      if f=1 then
         for j:=left to right-1 do  {上色}
             a[j]:=1
      else
         for j:=left to right-1 do  {去色}
             a[j]:=0;
     end;
for i:=1 to 2000 do     {计算被涂色的个数}
  if a[i]=1 then inc(sum);
writeln(sum);
close(input);close(output);
end.

6 楼

太复杂,看的都累

7 楼

线段树题目中有一道很经典的,是车票问题。。。

8 楼

有测试数据吗?

我来回复

您尚未登录,请登录后再回复。点此登录或注册