Някои примери (с решения) на проблеми с дървосегменти
Тази публикация е продължение на тази За решението моят код на сегментно дърво ще бъде използван с една модификация.
1. Дима и масива
Мама даде на момчето Дима масив с дължина n. Този масив не е прост, а специален. Дима може да избере две числа i и d (1 ≤ i ≤ n, -1000 ≤ d ≤ 1000) и елементът с индекс i магически става равен на d. Дима си играе с неговия масив, а майка му от време на време му задава въпроси – колко е сборът на всички числа в масива с индекси от f до t? Дима лесно се справи с тези въпроси, нали?
Спецификации
Входни данни
Първият ред съдържа две цели числа n и q (1 ≤ n ≤ 5•105, 1 ≤ q ≤ 105) — съответно броят на елементите в масива и общият брой операции и заявки. Следващият ред съдържа n числа a1, a2, . an (−1000 ≤ ai ≤ 1000) е началното състояние на масива. Следващите q реда съдържат операции и заявки. Първият знак в низа може да бъде = или ?. Ако низът започва с =, това е операция за присвояване. Това е последвано от i и d, ограниченията върху които са описани в условието. Ако низът започва с ?, това е заявка. Следват числата f и t(1 ≤ f, t ≤ n).
Изход
За всяка заявка отпечатайте сумата от числата в масива, индексирани от f до t, по един резултат на ред.
Това е един от класическите проблеми в DO. Сумата се използва като функция.
2. В страната на ненаучените уроци
Витя попадна в страна на ненаучени уроци. За да се върне у дома, той трябва да изпълни много задачи. В тази задача той трябва да спечели играта GCD срещу пазачите. Правилата на тази игра са много прости: има масив от естествени числа, след което играчите избират две числа l и r и трябва да изчислят най-големия общ делител (gcd) на всички елементи в масива с индексиот l до r включително. Който пресметне по-бързо, печели. За да избегнат измама, те понякога заменят някои числа в масива с други. Витя наистина иска да се прибере у дома, помогнете му с това, за което напишете програма, която много бързо ще изчисли GCD на даден интервал.
Спецификации
Входни данни
Първият ред съдържа броя на елементите n (1 ≤ n ≤ 105) в масива. Вторият ред съдържа n числа – елементи ai (1 ≤ ai ≤ 109) от масива. Третият ред съдържа броя заявки m (1 ≤ m ≤ 105). Тогава m реда съдържат три цели числа q, l, r (1 ≤ l ≤ r ≤ n). Ако q = 1, е необходимо да се изчисли НОД на елементи в интервала [l, r], ако q = 2, тогава е необходимо да се замени елементът в позиция l с числото r.
Изход
За всяка заявка с номер 1 отпечатайте отговора на заявката на отделен ред. Улика. Тук всичко е просто :)
Нека просто напишем функцията за най-голям общ делител и да я предадем като асоциативна функция за DO.
3. Заявка за вариация на диапазон
Последователността an е дадена със следната формула: an = n2 mod 12345 + n3 mod 23456. Трябва да отговорите много пъти на следните запитвания: • намерете разликата между максималните и минималните стойности между елементите ai, ai+1, . aj; • присвоете стойността j на елемента ai.
Спецификации
Входни данни
Първият ред съдържа естествено число k (k ≤ 100 000) — броят на заявките. Следващите k реда съдържат заявки, по една на ред. Заявка номер i се описва с две цели числа xi, yi. Ако xi > 0, тогава трябва да намерите разликата между максималната и минималната стойност сред елементите на axi. айи. В този случай 1 ≤ xi ≤ yi ≤ 100 000. Ако xi На английски На български