【SSLGZ 2644】线段树练习题一

问题描述
桌子上零散地放着若干个盒子，桌子的后方是一堵墙。如右图所示。现在从桌子的前方射来一束平行光， 把盒子的影子投射到了墙上。问影子的总宽度是多少？
样例输入
20 //桌面总宽度
4 //盒子数量
1 5
3 8
7 10
13 19
样例输出
15
算法讨论
构建一颗线段树，每个节点分别代表一个单位区间，我们给每个区间打上标记，当标记为1时代表此区间被完全覆盖，为0则没有，统计时如果当前区间标记为1，则把此区间长度加入到答案长度中。

const
  maxn=500000;
var
  t:array[1..maxn,1..3] of longint;
  i,n,m,x,y,s:longint;

function count(p:longint):longint;
begin
  if t[p,3]=1
    then count:=t[p,2]-t[p,1]
    else if t[p,2]-t[p,1]=1
           then count:=0
           else count:=count(p*2)+count(p*2+1)
end;

procedure insert(p,a,b:longint);
var
  m:longint;
begin
  if t[p,3]=0
    then begin
           m:=(t[p,1]+t[p,2]) div 2;
           if (t[p,1]=a) and (t[p,2]=b)
             then t[p,3]:=1
             else if b<=m
                    then insert(p*2,a,b)
                    else if a>=m
                           then insert(p*2+1,a,b)
                           else begin
                                  insert(p*2,a,m);
                                  insert(p*2+1,m,b)
                                end;
         end;
end;

procedure create(p:longint);
var
  m:longint;
begin
  if t[p,2]-t[p,1]>1
    then begin
           m:=(t[p,1]+t[p,2]) div 2;
           t[p*2,1]:=t[p,1]; t[p*2,2]:=m;
           t[p*2+1,1]:=m; t[p*2+1,2]:=t[p,2];
           create(p*2);
           create(p*2+1)
         end;
end;

begin
  read(n,m);
  t[1,1]:=1; t[1,2]:=n;
  create(1);
  for i:=1 to m do
    begin
      read(x,y);
      insert(1,x,y)
    end;
  s:=count(1);
  write(s)
end.

Pixiv ID：50484947