1. Сортировка и поиск

Разбор задачи 50. Закраска прямой

В этой задаче важную роль играет, где начинаются и заканчивается отрезки. Если мы отсортируем левые и правые концы отрезков и подсчитаем длину участков на прямой, покрытых хотя одним отрезком, то получим искомый результат.
Определение структур данных:

type info= 
  record 
    x: integer; { координата }
    p:integer; { 1 - отрезок начался, -1 - отрезок закончился }
  end;
var o:array[1..30000] of info; { массив для хранения концов отрезков,
      его размер в 2 раза больше числа отрезков }
  t:info; { временная переменная для обмена }
  s,l,r,n,i,j,k:integer;

Быстрая сортировка. Основная идея состоит в следующем. Разбиваем сортируемый массив на 3 части: элементы меньше некоторого значения `m`, элементы равные некоторому значению `m`, элементы больше некоторого значения `m`. После этого сортируем рекурсивно первую и третью часть. Выбирать значение `m` для разбиения нужно случайно из сортируемого массива. При выборе в качестве `m` первого значения или последнего элемента в массиве алгоритм будет работать за `O(N^2)` на уже упорядоченных массивах, а при выборе элемента из середины массива – можно также построить пример с временем работы `O(N^2)` (см. задачу 20. Анти-QuickSort).
Так как при каждом разбиении размеры сортируемой части уменьшаются примерно в 2 раза, то вложенность рекурсивных вызовов будет не более `log_2\ N`. На каждом уровне обрабатываются все `N` элементов по частям, таким образом время работы алгоритма будет равно `O(N\ log\ N)`.

procedure qsort(l,r:integer);
var i,j,m:integer;
begin
  if l>=r then  exit;
  m:=o[l+random(r-l+1)].x;
  i:=l;
  j:=r;
  while i<=j do
  begin
    while o[i].x<m  do  inc (i); { если элемент меньше m оставляем его в первой части }
    while o[j].x>m  do  dec (j); { если элемент больше m оставляем его в третьей части }
    { теперь i указывает на элемент, который не может находиться в первой части, 
      а j - на элемент, который не может находиться в третьей части }
    if i<=j then
    begin 
      t:=o[i];o[i]:=o[j];o[j]:=t; { меняем эти элементы местами }
      inc(i); dec(j); { переходим к следующим элементам }
    end;
  end;
  qsort(l,j); { сортируем первую часть }
  qsort(i,r); { сортируем третью часть }
end;

Ввод данных

  read(n);
  for i := 1 to n do
  begin
    read(l,r);
    o[i*2-1].x:=l;
    o[i*2-1].p:=1;
    o[i*2].x:=r;
    o[i*2].p:=-1;
  end;

Сортировка и подсчет

  qsort(1,2*n);
  k:=0;  
  s:=0; { длина окрашенной части прямой }
  for i := 1 to 2*n-1 do
  begin
    k:=k+o[i].p; { изменяем счетчик количества отрезков }
    if k>0 then { если начался отрезок или какой-то отрезок продолжается }
      s:=s+(o[i+1].x-o[i].x); { увеличим длину окрашенной части
                                на длину очередного интервала }
  end;
  writeln(s);