Торгівля#7482

Торгівля (Розбір)

Побудуємо дерево відрізків на діапазоні $[1; n]$ і спочатку обнулимо його. Нехай торговець продавав шапки в населених пунктах $[l_{i}; r_{i}]$ [l_i; r_i], починаючи з ціни $p_{i}$ p_i. Розіб'ємо відрізок $[l_{i}; r_{i}]$ [l_i; r_i] на фундаментальні відрізки $[l x_{1}; r y_{1}], [l x_{2}; r y_{2}], ..., [l x_{k}; r y_{k}]$ [lx_1; ry_1], [lx_2; ry_2], ..., [lx_k; ry_k]. Тоді у вершину, що відповідає відрізку $[l x_{q}; r y_{q}] (1 \leq q \leq k)$ [lx_q; ry_q]~(1 \le q \le k), заносимо число

p_{i} + сума довжин відрізків [l x_{t}; r y_{t}], для всіх t < q .

p_i + сума~довжин~відрізків~[lx_t; ry_t], для~всіх~t < q.

Наприклад, нехай $n = 5$ n = 5, і перша торгівля охоплює міста з номерами від $2$ до $5$ , починаючи з ціни $4$ . Тоді відрізок $[2; 5]$ розпадеться на фундаментальні: $[2; 2], [3; 3], [4; 5]$ [2; 2], [3; 3], [4; 5]. Після обробки першої операції дерево відрізків буде виглядати наступним чином:

Якщо фундаментальний відрізок $[a; b]$ містить значення $p$ , це означає, що:

торговець продавав шапки у всіх містах від $a$ до $b$ .
в місті $a$ шапка продавалася за ціною $p$ , у місті $a + 1$ a + 1 за ціною $p + 1$ p + 1, і так далі, аж до міста $b$ , де її ціна складала $p + b - a$ p + b - a.

Розглянемо процедуру обробки запиту $[l e f t; r i g h t]$ [left; right] (відрізка, на якому торговець веде торгівлю) на діапазоні $[l p os; r p os]$ [lpos; rpos], якщо початкова ціна шапки становить $x$ .

В лівому підвідрізку торговець буде продавати шапки в $l e n = min (mi d, r i g h t) - l e f t + 1$ len = min(mid, right) - left + 1 містах, починаючи з ціни $x$ . В правому підвідрізку перша ціна шапки в місті, куди прийде торговець, становитиме $x + l e n$ x + len. Таким чином, на відрізку з номерами $[ma x (l e f t, mi d + 1), r i g h t]$ [max(left, mid + 1), right] торгівля почнеться з ціни $x + l e n$ x + len. Однак якщо $l e n < 0$ len < 0 (що можливо, якщо весь відрізок запиту знаходиться в правому підвідрізку), слід покласти $l e n = 0$ len = 0.

Розглянемо відрізок $[a; b]$ , у якого є два підвідрізки: $[a; m]$ і $[m + 1; b]$ [m + 1; b]. Якщо в місті $a$ торговець продав шапку за ціною $p$ , то в місті $m + 1$ m + 1 її ціна становитиме $p + m + 1 - a$ p + m + 1 - a.

Під час обробки запитів реалізуємо проталкивання значень, що підтримує максимум.

Для виводу відповіді слід пройти по дереву, протиснути всі значення до листя і вивести їх.

Приклад

Розглянемо виконання двох запитів, наведених у прикладі. Розіб'ємо відрізки запитів на фундаментальні:

$[1; 3] = [1; 3]$ [1; 3] = [1; 3];
$[2; 4] = [2; 2] + [3; 3] + [4; 4]$ [2; 4] = [2; 2] + [3; 3] + [4; 4].

Реалізація алгоритму

Оголосимо масив $S e g T r ee$ SegTree для зберігання дерева відрізків.

#define MAX 300010
long long SegTree[4*MAX];

Функція Push виконує проталкивання значення з вершини $v$ в її нащадків.

void Push(int v, int lpos, int mid, int rpos)
{
  if (SegTree[v])
  {
    SegTree[2 * v] = max(SegTree[2 * v], SegTree[v]);
    SegTree[2 * v + 1] = max(SegTree[2 * v + 1], 
                             SegTree[v] + mid - lpos + 1);
    SegTree[v] = 0;
  }
}

C++

Функція Update виконує продаж шапок на проміжку $[l e f t; r i g h t]$ [left; right], починаючи з ціни $x$ .

void Update(int v, int lpos, int rpos, int left, int right, 
            long long x)
{
  if (left > right) return;
  if ((lpos == left) && (rpos == right))
    SegTree[v] = max(SegTree[v], x);
  else
  {
    int mid = (lpos + rpos) / 2;
    Push(v, lpos, mid, rpos);

    int len = min(mid, right) - left + 1;
    if (len < 0) len = 0;
    Update(2 * v, lpos, mid, left, min(mid, right), x);
    Update(2 * v + 1, mid + 1, rpos, max(left, mid + 1), 
                                         right, x + len);
    }
}

C++

Функція PrintResult проталкиває значення з внутрішніх вершин до листків і виводить підсумковий стан масиву.

void PrintResult(int v, int lpos, int rpos)
{
  if (lpos == rpos)
    printf("%lld ", SegTree[v]);
  else
  {
    int mid = (lpos + rpos) / 2;
    Push(v, lpos, mid, rpos);

    PrintResult(2 * v, lpos, mid);
    PrintResult(2 * v + 1, mid + 1, rpos);
  }
}

C++

Основна частина програми. Читаємо вхідні дані.

scanf("%d %d", &n, &m);
memset(SegTree,0,sizeof(SegTree));

Обробляємо $m$ запитів.

for(i = 0; i < m; i++)
{
  scanf("%d %d %lld", &l, &r, &x);
  Update(1,1,n,l,r,x);
}

Виводимо результат.

PrintResult(1,1,n);
printf("\n");