题意/Description：

 

    桌子上零散地放着若干个盒子，桌子的后方是一堵墙。如右图所示。现在从桌子的前方射来一束平行光， 把盒子的影子投射到了墙上。问影子的总宽度是多少？

 

 

读入/Input：

不详

 

20   //桌面总宽度

4    //盒子数量

1 5

3 8

7 10

13 19

 

输出/Output：

    影子的总宽度是多少（15）

 

题解/solution：

    给线段树每个节点增加一个域cover。cover=1表示该结点所对应的区间被完全覆盖，cover=0表示该结点所对应的区间未被完全覆盖。

 

代码/Code：

type  arr=record    l,r:longint;    cover:longint;  end;var  tree:array [0..2001] of arr;  n,m:longint;procedure ins(p,a,b:longint);var  m:longint;begin  with tree[p] do    begin      if cover=0 then        begin          m:=(l+r) div 2;          if (l=a) and (r=b) then cover:=1 else            begin              if b<=m then ins(p*2,a,b) else                if a>=m then ins(p*2+1,a,b) else                  begin                    ins(p*2,a,m);                    ins(p*2+1,m,b);                  end;            end;        end;    end;end;function count(p:longint):longint;begin  with tree[p] do    begin      if cover=1 then count:=r-l else        if r-l=1 then count:=0 else          count:=count(p*2)+count(p*2+1);    end;end;procedure cre(p:longint);var  m,k:longint;begin  k:=p*2;  with tree[p] do    begin      if r-l>1 then        begin          m:=(l+r) div 2;          tree[k].l:=l;          tree[k].r:=m;          tree[k+1].l:=m;          tree[k+1].r:=r;          cre(p*2);          cre(p*2+1);        end;    end;end;procedure main;var  i,x,y:longint;begin  readln(m);  tree[1].l:=1; tree[1].r:=m;  cre(1);  readln(n);  for i:=1 to n do    begin      readln(x,y);      ins(1,x,y);    end;end;begin  main;  write(count(1));end.