e-olymp 4482. В стране невыученных уроков 2

Задача

Теперь у Вити есть программа, которая помогает ему быстро находить НОД многих чисел. Поэтому стражи решили изменить правила: теперь Витя должен найти наибольший общий делитель (НОД) чисел на промежутке [l; r], а стражи – наименьшее общее кратное (НОК), у кого получится число меньше, тот и выиграет.

Входные данные

Первая строка содержит количество элементов в массивеn (1n106). Во второй строке находится n чисел – элементы ai (1ai109) массива. В третьей строке находится количество запросовm (1m 105). Далее в m строках находится по три числа q, l, r (1lrn). Если q = 1, требуется определить победителя для промежутка [l; r], если q = 2, то нужно заменить элемент в позиции l на число r.

Выходные данные

Для каждого запроса с номером 1 в отдельной строке выведите строку «wins«, если Витя выиграл, строку «loser«, если он проиграл и «draw«, если была ничья.

Решение

В данной задаче нам нужно реализовать дерево отрезков, но поменять функцию которую определяет значение в узлах. Прочитав условие можно понять, что ответ «loser» мы не выведем никогда, так как НОД не может быть больше НОК. Тогда остается определить когда выводить «wins» или «draw». НОД и НОК некоторого количества чисел равны тогда и только тогда, когда все числы для которых мы считаем НОД и НОК равны между собой. Поэтому ассоциативной функцией для построения дерева выберем функцию равенства, если числа равны возвращаем само число, иначе 0. Тогда для ответа на вопрос задачи просто следует узнать что находится в соответсвующем узле.
Если это 0, то НОК больше НОД, иначе они равны и мы выведем «draw».

Код

Тесты

Входные данные Выходные данные
5
2 4 6 10 8
6
1 1 5
1 2 3
2 5 15
2 3 10
1 3 5
1 1 1
wins
wins
wins
draw
5
7 7 7 7 7
4
1 1 5
2 2 1
1 1 5
1 3 5
draw
wins
draw

Задача взята отсюда.

Решенная задача на e-olymp.

Код программы.

 

e-olymp 4481. В стране невыученных уроков

Задача

Витя попал в страну невыученных уроков. Для того, чтобы вернуться домой ему нужно выполнить множество заданий. В этой задаче он должен выиграть у стражей в НОД-игру. Правила этой игры очень простые: есть массив натуральных чисел, после чего игроки выбирают два числа [latex]l[/latex] и [latex]r[/latex], и им надо посчитать наибольший общий делитель (НОД) всех элементов в массиве с индексами от [latex]l[/latex] до [latex]r[/latex] включительно. Кто быстрее посчитает, тот и выиграл. Чтобы избежать нечестных игр, они иногда заменяют некоторые числа в массиве на другие.

Витя очень хочет домой, помогите ему в этом, для чего напишите программу, которая будет очень быстро считать НОД на заданном промежутке.

Входные данные

Первая строка содержит количество элементов [latex]n[/latex] [latex](1\leq n\leq 10^5)[/latex] в массиве. Во второй строке находится [latex]n[/latex] чисел – элементы [latex]a_i[/latex] [latex](1\leq a_i\leq 10^9)[/latex] массива. В третьей строке находится количество запросов [latex]m[/latex] [latex](1\leq m\leq 10^5)[/latex]. Далее в [latex]m[/latex] строках находятся по три числа [latex]q[/latex], [latex]l[/latex], [latex]r[/latex] [latex](1\leq l\leq r\leq n)[/latex]. Если [latex]q=1[/latex], требуется посчитать НОД элементов на промежутке [latex][l,r][/latex], если [latex]q=2[/latex], то надо заменить элемент в позиции [latex]l[/latex] на число [latex]r[/latex].

Выходные данные

Для каждого запроса с номером [latex]l[/latex] в отдельной строке выведите ответ на запрос.

Тесты

Входные данные: Выходные данные:
5
2 4 6 10 8
6
1 1 5
1 2 3
2 5 15
2 3 10
1 3 5
1 1 5
2
2
5
1

Код программы

Алгоритм решения

Данная задача решена с помощью структуры данных «дерево отрезков». В каждой вершине дерева храним НОД всех чисел на соответствующем отрезке массива. Функции, отвечающие за построение самого дерева отрезков, нахождение  НОД на отрезке и запрос на модификацию элемента являются рекурсивными.  Дерево строим следующим образом: листьями данного дерева будут сами элементы исходного массива, а значения элементов, находящихся на уровень выше, будут представлять собой НОД двух соседних листов. Таким же образом считаем значения вершин следующего уровня и т.д. Чтобы найти НОД на заданном отрезке рассматриваем случаи расположения данного отрезка. Он может полностью принадлежать одному потомку, а может быть разбит между правым и левым потомками. В первом случае функцию запускаем от одного потомка и получаем требуемое, во втором случае функцию запускаем от двух потомков и находим от полученных результатов НОД. При выполнении запроса на модификацию запускаем функцию от корня, спускаемся до требуемого элемента, изменяем его, и поднимаемся обратно к корню, модифицируя значения вершин, для которых данный элемент является подотрезком.

В самой задаче, в зависимости от требуемого, в цикле находим НОД на заданном отрезке или выполняем модификацию элемента.

Для получения подробной информации о структуре данных «Дерево отрезков» можно перейти по данной ссылке
Ссылка на засчитанное решение на e-olymp
Ссылка на условие задачи
Ссылка на решение задачи на ideone.com

e-olymp 4082. Произведение на отрезке

Условие задачи

Это нормально чувствовать себя взволнованным и напряженным за день до олимпиады по программированию. Чтобы расслабиться, вы пошли выпить со своими друзьями в соседний паб. Для сохранения остроты ума до следующего дня, Вы решили сыграть в следующую игру. Для начала Ваши друзья написали последовательность [latex] n [/latex] целых чисел [latex] x_{1}, x_{2},\cdots , x_{n} [/latex]. Потом следует  [latex] k [/latex] раундов, на каждом из которых выполняется одна из следующих команд:

  • команда изменения, когда необходимо изменить одно значение в последовательности;
  • команда умножения, когда по заданным значениям [latex] i [/latex] и [latex] j [/latex] необходимо определить, является ли произведение [latex] x_{i}\cdot x_{i+1} \cdot \; \; \cdots \; \; \cdot x_{j-1} \cdot x_{j} [/latex] положительным, отрицательным или равным нулю.

Так как Вы находитесь в пабе, то штрафом за неправильный ответ будет употребление дополнительной пинты пива. Вы беспокоитесь, что это может негативно повлиять на Вас при участии в конкурсе на следующий день, и у Вас нет желания проверять на корректность теорию пика Баллмера. К счастью, друзья разрешили Вам пользоваться ноутбуком. Поскольку Вы больше доверяете Вашим способностям программировать, нежели математике, то было решено написать программу, которая поможет сыграть в игру.

Входные данные

Каждый тест состоит из нескольких строк. Первая строка каждого теста содержит два числа [latex] n [/latex]  и [latex] k [/latex]   ([latex] 1\leq n,k\leq 10^{5}[/latex]) — количество элементов в последовательности и число раундов в игре. Вторая строка содержит [latex] n [/latex] целых чисел [latex] x_{i} [/latex] — начальные значения последовательности ([latex] -100\leq x_{i}\leq 100[/latex] для [latex]i=1,2, \cdots ,n[/latex]). Каждая из следующих [latex] k [/latex]  строк описывает команду, начинающуюся заглавной буквой  [latex] C [/latex] или [latex] C [/latex]. Если это буква [latex] C [/latex], то строка содержит команду замены, за буквой следуют два числа [latex] i [/latex] и [latex] v [/latex], указывающих на то что [latex] x_{i} [/latex] необходимо заменить на [latex] v [/latex] ([latex] 1\leq i\leq n[/latex] и [latex]-100\leq v\leq 100[/latex]). Если это буква [latex] P [/latex], то строка задает команду умножения, за буквой следуют два числа [latex] i [/latex] и [latex] j [/latex] — необходимо вычислить произведение от [latex] x_{i} [/latex] до [latex] x_{i} [/latex] включительно ([latex] 1\leq i\leq j\leq n [/latex]) . Каждый тест содержит как минимум одну команду умножения.

Выходные данные

Для каждого теста вывести одну строку, содержащую ответы на все команды умножения. [latex] i [/latex]-ый символ строки является результатом [latex] i [/latex]-ой команды умножения. Если произведение положительно, то вывести символ [latex] + [/latex] (плюс); если произведение отрицательно, то вывести [latex] — [/latex] (минус); если произведение равно нулю, то вывести [latex] 0 [/latex] (ноль).

Тесты

Входные данные Выходные данные
4 6

-2 6 0 -1

C 1 10

P 1 4

C 3 7

P 2 2

C 4 -5

P 1 4

5 9

1 5 -2 4 3

P 1 2

P 1 5

C 4 -5

P 1 5

P 4 5

C 3 0

P 1 5

C 4 -5

C 4 -5

0+-

+-+-0

5 5

10 -2 0 5 1

C 1 0

P 1 4

C 2 7

P 1 1

C 2 0

00
6 4

0 20 0 30 0 -10

P 2 2

P 2 3

P 3 6

P 2 6

4 3

0 -1 -2 0

P 2 3

C 1 9

P 1 2

3 3

5 2 0

C 1 7

C 3 0

C 1 0

6 5

100 10 55 11 0 -33

P 1 4

C 5 6

C 3 72

C 5 -20

P 5 6

+000

+-

 

++

Код программы

Решение

Данная задача решается при помощи стандартного алгоритма по теме «Дерево отрезков» (данный алгоритм можно посмотреть на сайте e-maxx). Следовательно, при построении дерева сначала считывается массив, а после выполняется построение дерева (от корня). В том случае, если функция, строящая дерево, вызывалась от листа,  все значения элементов массива записываются в дерево как [latex]1[/latex], если элемент больше нуля, если меньше нуля, то записывается как [latex]-1[/latex], а в случае равенства элемента нулю, он записывается [latex]0[/latex] (нулём).  В ином случае (если функция вызывалась не от листа), она начинает вызываться рекурсивно от каждого из двух сыновей и перемножает вычесленные значения.

Для выполнения функции изменения элемента ей (функции) передаётся текущая вершина. Затем выполняется вызов из сына, сожержащего элемент с данным номером. Таким образом процесс доходит до листа, которому и присваевается значение. При чём, аналогично построению дерева, элементы записываются как [latex]1[/latex],[latex]-1[/latex] или же [latex]0[/latex].

Для выполнения команды умножения проверяется интервал запроса. В том случае, если они равны интервалам отрезка, возвращается значение элемента (вершины) с соответствующим индексом. Иначе, вызывается рекурсивная функция, которая запускается  от правого, если границы запроса лежать в правом отрезке, или от левого сына текущей вершины, если, соответственно, границы исходного запроса лежат в левом отрезке. Рекурсивная функция перемножает полученные результаты в том случае, если она запускает и от левого, и от правого сыновей (т.е. интервал запроса принадлежит пересечению интервалов отрезка).

Далее  (в программе) идёт процесс построения дерева и выполнение действий, удовлетворяющих команды, описанные в уловии задачи.

Ссылки

  • Рабочий код на Ideone.com
  • Засчитанное решение на e-olymp.com
  • При ришении данной задачи был использован материал по структурам данных «дерево отрезков» с сайта e-maxx.ru
  • Задача взята с сайта e-olymp.com

e-olymp 2941. Дима и массив

Задача взята с сайта e-olymp.com

Условие задачи

Мама подарила мальчику Диме массив длины [latex]n[/latex]. Массив этот не простой, а особенный. Дима может выбрать два числа [latex]i[/latex] и [latex]d[/latex] ([latex]1\leq i\leq n[/latex], [latex]-1000\leq d\leq 1000[/latex]), и элемент с индексом [latex]i[/latex] магически становится равным [latex]d[/latex]. Дима играет со своим массивом, а мама время от времени задает ему вопросы — какова сумма всех чисел в массиве с индексами от [latex]f[/latex] до [latex]t[/latex]? Дима легко справился с этими вопросами, сможете ли Вы?

Входные данные

В первой строке находятся два целых числа [latex]n[/latex] и [latex]q[/latex] [latex]1\leq n\leq 5\cdot 10^{5},~1\leq q\leq 10^{5}[/latex] — количество элементов в массиве и суммарное количество операций и запросов соответственно. В следующей строке дано [latex]n[/latex] чисел [latex]a_{1},a_{2},\ldots,a_{n}[/latex] [latex]\left ( -1000\leq a_{i}\leq 1000 \right )[/latex] — начальное состояние массива. В следующих [latex]q[/latex] строках заданы операции и запросы. Первый символ в строке может быть [latex]=[/latex] или [latex]?[/latex]. Если строка начинается с [latex]=[/latex], то это операция присваивания. Далее следуют [latex]i[/latex] и [latex]d[/latex], ограничения на которые описаны в условии. Если строка начинается с [latex]?[/latex], то это запрос. Далее следуют числа [latex]f[/latex] и [latex]t[/latex] [latex]\left (1\leq f,~t\leq n \right )[/latex].

Выходные данные

Для каждого запроса выведите сумму чисел в массиве с индексами от [latex]f[/latex] до [latex]t[/latex], по одному результату в строке.

Тесты

Входные данные Выходные данные
3 3
1 2 3
? 1 3
= 3 2
? 1 3
6
5
5 3
1 2 3 4 5
? 1 5
= 1 7
? 1 3
15
12
5 6
1 2 3 4 5
? 1 5
= 1 0
? 1 5
= 2 7
? 1 5
? 1 3
15
14
19
10

Код программы

ideone.com

Засчитанное решение на e-olymp.com.

Решение

Для решения данной задачи необходимо воспользоваться структурой данных «дерево отрезков».

Для построения дерева считываем исходный массив, затем запускаем функцию построения от корня дерева. Если длина массива не равна единице или функция была запущена не от листа, то она вызывается рекурсивно от каждого из двух сыновей и суммирует вычисленные значения. Если функция построения была вызвана от листа, то значения элементов массива записываются в дерево.

Для операции присваивания передаем рекурсивной функции  текущую вершину дерева и она выполняет вызов от одного из своих сыновей, который содержит элемент с данным индексом. Пересчитывает суммы и доходит до листа, которому присваивается новое значение.

Для выполнения запроса суммы также используется рекурсивная функция. Она запускается либо от правого, либо от левого сына текущей вершины, если границы исходного запроса лежат в одном из их отрезков. Либо запускается от обоих сыновей, если границы исходного запроса принадлежат пересечению их отрезков, суммируя результаты двух запросов. Таким образом функция доходит до отрезка, границы которого совпадают с текущим запросом или до листа и возвращает их значение.

Для решения данной задачи были использованы материалы сайта e-maxx.ru.

e-olimp №2907. Можете ли Вы ответить на эти вопросы — 3

Условие

Задана последовательность целых чисел [latex]a_1, a_2, \ldots, a_n[/latex] ([latex]| a_i | \le 10000[/latex], [latex]1 \le n \le 50000[/latex]). Над ней Вам следует выполнить [latex]m[/latex] ([latex]m \le 50000[/latex]) операций:

  • модифицировать [latex]i[/latex]-ый элемент последовательности
  • для заданных [latex]x[/latex] и [latex]y[/latex] вывести [latex]MAX[/latex] [latex]\{ a_i + a_{i+1} + \ldots + a_j[/latex], [latex]x \le i \le j \le y \}[/latex]

Входные данные

Первая строка содержит значение n. Следующая строка содержит n целых чисел, задающих последовательность [latex]a_1, a_2, \ldots, an[/latex]. Третья строка содержит число [latex]m[/latex]. Следующие [latex]m[/latex] строк содержат запросы вида:

  • [latex]0[/latex] [latex]x[/latex] [latex]y[/latex]: изменить [latex]a_x[/latex] на [latex]y[/latex] ([latex]| y | \le 10000[/latex]).
  • [latex]1[/latex] [latex]x[/latex] [latex]y[/latex]: вывести [latex]MAX[/latex] [latex]\{ a_i + a_{i+1} + \ldots + a_j, x \le i \le j \le y \}[/latex]

Код программы

Для запроса на выполнение программы нажать здесь.

Ссылка на использованный алгоритм.

Ссылка на засчитанное решение.

e-olymp 2307. The sum

The array of [latex]n[/latex] elements is given. Find the sum of numbers on a segment.

Input

The first line contains two integers [latex]n[/latex] and [latex]k[/latex] [latex](1 \le n \le 10^5, 0 \le k \le 10^5)[/latex] — the number of elements in array and the number of queries. The next [latex]k[/latex] lines contain the queries of two forms:

  • [latex]A[/latex] [latex]l[/latex] [latex]r[/latex] [latex]x[/latex]  — assign the value of [latex]x[/latex] to each element form position [latex]l[/latex] to [latex]r[/latex] [latex](1 \le l \le r \le n, 0 \le x \le 10^9)[/latex]
  • [latex]Q[/latex] [latex]l[/latex] [latex]r[/latex] — find the sum of array elements on positions from [latex]l[/latex] to [latex]r[/latex] [latex](1 \le l \le r \le n)[/latex]

Initially the array is filled with zeroes.

Output

For each query of the form «[latex]Q[/latex] [latex]l[/latex] [latex]r[/latex]» print the sum of numbers on a segment.

Tests

Input Output
1 5 9
A 2 3 2
A 3 5 1
A 4 5 2
Q 1 3
Q 2 2
Q 3 4
Q 4 5
Q 5 5
Q 1 5
3
2
3
4
2
7
2 10 6
A 1 10 1
Q 1 10
A 1 5 2
Q 1 10
A 4 7 3
Q 1 10
10
15
21
3 100000 2
A 1 100000 1000000000
Q 1 100000
100000000000000

Algorithm

After reading the statement of the problem it is understandable that we should implement segment tree with support for multiple modification request — assignment. To make modifications to the whole segment and quickly answer for the amounts queries, we organize data structure in which each node store «colored» — if it is painted in any color or not and a sum on corresponding to this node segment.

Under the node coloring we will understand that all segment with all its subsegments should be colored in the appropriate color (assigned a specific number). Also define the mark that the node isn’t colored (in the code defined as WHITE), for example, any negative number, because queries contain only positive. This implementation allows us to do «delayed» update of the tree. Specifically, for each request of modification, instead of changing the values at all vertices where it is required, change only some of them, leaving «colored» markers for the other segments, which means that the whole segment with its subsegments should be painted in this color.
But if we do it so, after each modification request segment tree will stop being up to date. For resolving this problem, organise a function, that will «push» information from parents to children: void push(Node *tree, int currentNode, int left, int right) . This function is called during requests processing to update the appropriate values:

  • assign parent’s color to the children
  • recalculate the amount of the segment for children (as the length of the segment multiplied by the current color (number))
  • set parent node as uncolored

Thus, to solve this task, we need two usual for segment tree functions:

  • void update(Node *tree, int currentNode, int left, int right, int leftBorder, int rightBorder, int color)
  • long long sum(Node *tree, int currentNode, int left, int right, int leftBorder, int rightBorder)

With the difference that, when we are going down by the tree, pushes information only as far as necessary (it should be noted, that in this way the asymptotic doesn’t impair and remains standard [latex]O(\log n)[/latex]).

Rest details of the implementation can be found in the code of the program or in the sources of information listed at the end of the article.

Footnote: such realization, where the problem constraints too large queries, and in the current version when we update a range and only mark its child that it needs to be updated and update it when needed, usually calls lazy propagation. This approach allows us to solve a variety of new at first glance seemed complex tasks. More information listed at the end of the article.

Code

Links