Козленятко, яке вчилось рахувати (Розбір)

Малюк може обрати двох пасажирів на відрізку [l; r] тоді і тільки тоді, коли сума двох найменших мас тварин на цьому відрізку не перевищує $k$. Дійсно, якщо якась пара тварин підходить, то пара з двох найлегших тварин підходить тим більше.

Тому можна побудувати дерево відрізків, у якому кожна вершина зберігає два мінімуми на своєму відрізку. Однак нас цікавлять не самі мінімуми, а лише те, чи існують два числа, сума яких не перевищує $k$. Це дозволяє зберігати в кожній вершині лише одне число.

Значення у вершинах. Листки дерева відрізків зберігають маси тварин. Кожна внутрішня вершина зберігає:

• $0$, якщо її відрізок містить двох тварин із сумарною масою, що не перевищує $k$;

• мінімальну масу тварини на своєму відрізку в іншому випадку.

Маси тварин додатні, тому значення $0$ не збігається з жодною масою і однозначно означає, що знайдено відповідну пару.

Об'єднання дітей. Значення вершини обчислюється зі значень $x$ та $y$ її дітей. Відповідна пара тварин на відрізку вершини або повністю лежить в одній з її половин, або складається з тварини з лівої половини та тварини з правої половини. Тому:

• якщо x = 0 або y = 0, відповідна пара лежить в одній із половин, і значення вершини дорівнює $0$;

• інакше, $x$ та $y$ — це мінімальні маси в половинах, і найкраща пара тварин з різних половин має сумарну масу x + y. Якщо x + y \le k, значення вершини дорівнює $0$, інакше воно дорівнює \min(x, y).

Із такою функцією об'єднання задача розв'язується стандартним деревом відрізків із точковими оновленнями.

Для запиту типу $1$ відповідь "Yes", якщо значення на відрізку [l; r] дорівнює $0$, і "No" в іншому випадку.

Приклад

Розглянемо запити з прикладу, k = 9. Спочатку маси тварин дорівнюють 1, 3, 1, 6, 6, 7:

• $116$: дві найлегші тварини мають маси $1$ та $1$, 1 + 1 = 2 \le 9, відповідь "Yes";

• $112$: 1 + 3 = 4 \le 9, відповідь "Yes";

• $247$: маса четвертої тварини стає $7$;

• $145$: 7 + 6 = 13 > 9, відповідь "No";

• $156$: 6 + 7 = 13 > 9, відповідь "No";

• $217$ та $238$: маси першої та третьої тварин стають $7$ та $8$.

Перед останнім запитом $116$ маси тварин дорівнюють 7, 3, 8, 7, 6, 7. Дерево відрізків для них показано нижче. Для кожної вершини показано її відрізок та збережене значення. Листки виділено жовтим кольором, а вершину зі значенням $0$ — помаранчевим.

Обчислимо значення у внутрішніх вершинах:

• $[1;2]$: 7 + 3 = 10 > 9, значення дорівнює \min(7, 3) = 3;

• $[1;3]$: 3 + 8 = 11 > 9, значення дорівнює \min(3, 8) = 3;

• $[4;5]$: 7 + 6 = 13 > 9, значення дорівнює \min(7, 6) = 6;

• $[4;6]$: 6 + 7 = 13 > 9, значення дорівнює \min(6, 7) = 6;

• $[1;6]$: 3 + 6 = 9 \le 9, значення дорівнює $0$.

Лише вершина $[1;6]$ містить $0$: дві найлегші тварини з масами $3$ та $6$ знаходяться в різних половинах відрізка, і їхня сумарна маса дорівнює $9$. Тому відповідь на останній запит — "Yes".

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

Оголосимо константи та робочі масиви. Масив SegTree зберігає дерево відрізків, а маси тварин зберігаються в масиві $a$. Константа $INF$ більша за будь-яку масу тварини і використовується як нейтральний елемент для порожнього відрізка. Сума $INF$ та будь-якої маси не перевищує 2 \cdot 10^9 + 10 і вміщується в тип $int$.

#define MAX 1000001
#define INF 1000000010
int SegTree[4 * MAX];
int a[MAX];

Функція f об'єднує значення $x$ та $y$ дітей. Якщо хоча б одна з дітей містить $0$, її відрізок уже містить двох відповідних пасажирів. Якщо x + y \le k, найлегші тварини лівої та правої половин утворюють відповідну пару. В обох випадках повертається $0$; інакше повертається мінімум з $x$ та $y$.

int f(int x, int y)
{
  if (x == 0 || y == 0 || x + y <= k) return 0;
  return min(x, y);
}

Функція BuildTree будує дерево відрізків з масиву $a$. Вершина $v$ відповідає відрізку [lpos; rpos]. Листки зберігають маси тварин, а значення у внутрішніх вершинах обчислюються функцією $f$.

void BuildTree(int v, int lpos, int rpos)
{
  if (lpos == rpos)
    SegTree[v] = a[lpos];
  else
  {
    int mid = (lpos + rpos) / 2;
    BuildTree(2 * v, lpos, mid);
    BuildTree(2 * v + 1, mid + 1, rpos);
    SegTree[v] = f(SegTree[2 * v], SegTree[2 * v + 1]);
  }
}

Функція Query повертає значення на відрізку [left; right]: $0$, якщо він містить двох пасажирів із сумарною масою не більше $k$, і мінімальну масу тварини в іншому випадку. Вершина $v$ відповідає відрізку [lpos; rpos]. Для порожнього відрізка повертається нейтральне значення $INF$.

int Query(int v, int lpos, int rpos, int left, int right)
{
  if (left > right) return INF;
  if ((lpos == left) && (rpos == right)) return SegTree[v];
  int mid = (lpos + rpos) / 2;
  return f(Query(2 * v, lpos, mid, left, min(right, mid)),
           Query(2 * v + 1, mid + 1, rpos, max(left, mid + 1), right));
}

Функція Update присвоює значення $val$ елементу з індексом $pos$ та перераховує значення в усіх вершинах на шляху від листка до кореня. Вершина $v$ відповідає відрізку [lpos; rpos].

void Update(int v, int lpos, int rpos, int pos, int val)
{
  if (lpos == rpos)
     SegTree[v] = val;
  else
  {
    int mid = (lpos + rpos) / 2;
    if (pos <= mid) Update(2 * v, lpos, mid, pos, val);
    else Update(2 * v + 1, mid + 1, rpos, pos, val);
    SegTree[v] = f(SegTree[2 * v], SegTree[2 * v + 1]);
  }
}

Основна частина програми. Зчитаємо кількість тварин $n$ та залишкову вантажопідйомність $k$. Зчитаємо маси тварин у масив $a$, починаючи з індексу $1$.

scanf("%d %d", &n, &k);
for (i = 1; i <= n; i++)
  scanf("%d", &a[i]);

Побудуємо дерево відрізків з елементів масиву a[1 \ldots n].

BuildTree(1, 1, n);

Обробимо $q$ запитів по черзі. Тварини нумеруються, починаючи з $1$, і елементи масиву $a$ також зберігаються, починаючи з індексу $1$, тому індекси із запитів використовуються без змін.

scanf("%d", &q);
for (j = 0; j < q; j++)
{
  scanf("%d %d %d", &t, &l, &r);

Запит типу $1$: обчислимо значення на відрізку [l; r]. Якщо воно дорівнює $0$, двох пасажирів знайдено.

  if (t == 1)
  {
    int Res = Query(1, 1, n, l, r);
    if (Res == 0) printf("Yes\n"); else printf("No\n");
  }

Запит типу $2$: присвоїмо масу $r$ тварині з індексом $l$.

  else
    Update(1, 1, n, l, r);
}