回 帖 发 新 帖 刷新版面

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

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

错的
比如说
3
1 1 3
0 1 512
1 256 512
你得到的-258
就算if tree[i].s=1 then s:=s+(tree[i].a-tree[i].b)
改对了你也得到的是258 还是错了

5 楼

1000*2000
这么小的数据范围 有必要用线段树么

6 楼

Program Sample1; 
Const Maxn=120000;  {最多支持120000条线段,即支持Long_x<=60000} 
Type TreeNode=Record 
                a,b,Left,Right:Longint; 
                Cover,bj:shortint; {记录线段是否被覆盖;线段的标记} 
              End; 
Var i,j,k,m,n,tot,c,d,Ans:longint; 
    Tree:array[0..Maxn] of TreeNode; 
Procedure MakeTree(a,b:Longint); {建立线段树的过程} 
Var Now:longint; 
Begin 
  inc(tot); 
  Now:=tot; 
  Tree[Now].a:=a; 
  Tree[Now].b:=b; 
  if a+1<b then 
  begin 
    Tree[Now].Left:=tot+1; 
    MakeTree(a,(a+b) shr 1); 
    Tree[Now].Right:=tot+1; 
    MakeTree((a+b) shr 1,b); 
  end; 
End; 
Procedure Init;  {读入数据并预处理的过程} 
Begin 
  assign(input,'sample1.in'); 
  reset(input); 
  assign(output,'sample1.out'); 
  rewrite(output); 
  readln(n,m); 
  fillchar(Tree,sizeof(Tree),0); 
  tot:=0; 
  MakeTree(1,n); 
End; 
Procedure Clean(Num:Longint);  {更新标记的过程} 
Begin 
  Tree[Num].Cover:=0; 
  Tree[Num].bj:=0; 
  Tree[Tree[Num].Left].bj:=-1;   Tree[Tree[Num].Right].bj:=-1; 
End; 
Procedure Insert(Num,c,d:longint);  {涂色的过程} 
Var Mid:longint; 
Begin 
  if Tree[Num].bj=-1 then Clean(Num); {若被标记则更新} 
  if Tree[Num].Cover=1 then exit; {若线段已被涂色,退出过程} 
  if (c<=Tree[Num].a)and(d>=Tree[Num].b) then 
  begin 
    Tree[Num].Cover:=1; 
    exit; 
  end; 
  Mid:=(Tree[Num].a+Tree[Num].b) shr 1; 
  if c<Mid then Insert(Tree[Num].Left,c,d); 
  if d>Mid then Insert(Tree[Num].Right,c,d); 
End; 
Procedure Delete(Num,c,d:Longint);  {擦除颜色的过程} 
Var Mid:Longint; 
Begin 
  if Tree[Num].bj=-1 then Exit; {若线段被标记,说明该线段已不复存在,无需再进
行删除,退出过程} 
  if (c<=Tree[Num].a)and(d>=Tree[Num].b) then 
  begin 
    Tree[Num].Cover:=0; 
    Tree[Tree[Num].Left].bj:=-1; 
    Tree[Tree[Num].Right].bj:=-1;{把线段已被删除的信息传给左右儿子} 
    exit; 
  end; 
  if Tree[Num].Cover=1 then  {若该线段是被涂了色的} 
  begin 
    Tree[Num].Cover:=0; 
    Tree[Tree[Num].Left].bj:=-1; 
    Tree[Tree[Num].Right].bj:=-1;     {先删除} 
    if Tree[Num].a<c then Insert(Num,Tree[Num].a,c); {再插入} 
    if d<Tree[Num].b then Insert(Num,d,Tree[Num].b); 
  end 
  else  {否则继续对左右儿子调用删除过程} 
  begin 
    Mid:=(Tree[Num].a+Tree[Num].b) shr 1; 
    if c<Mid then Delete(Tree[Num].Left,c,d); 
    if d>Mid then Delete(Tree[Num].Right,c,d); 
  end; 
End; 
Procedure Calculate(Num:longint);{计算被覆盖的单位线段条数的过程} 
Begin 
  if Num=0 then exit; {父亲已是叶子结点了(叶子节点的儿子为0),返回} 
  if Tree[Num].bj=-1 then exit; {线段被标记,说明已不存在,返回} 
  if Tree[Num].Cover=1 then 
  begin 
    inc(Ans,Tree[Num].b-Tree[Num].a); 
    exit; 
  end; 
  Calculate(Tree[Num].Left); 
  Calculate(Tree[Num].Right); 
End; 
Procedure Main;   {主过程} 
Var i,k:longint; 
Begin 
  for i:=1 to m do 
  begin 
    readln(k,c,d); 
    if k=1 then Insert(1,c,d) 
    else Delete(1,c,d); 
  end; 
  Ans:=0; 
  Calculate(1); 
  Writeln(Ans); 
  Close(output); 
End; 
Begin   {主程序} 
  Init; 
  Main; 
End. 

7 楼

呵呵,今天做了一个线段树的题目,但还是没十分弄懂!!

8 楼

呵呵,看了半天,题义还没看懂。

我来回复

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