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-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

e-olymp 2906. Can you answer these queries — 1

You are given an integer sequence.

[latex]a_1, a_2, \ldots, a_n (|a_i| \le 15007, 1 \le n \le 50000)[/latex].

A query is defined as follows:

[latex]Query(x, y) = MAX (a_i + a_{i+1} + \ldots + a_j, x \le i \le j \le y)[/latex]

Given [latex]m[/latex]  queries, your program must output the results of these queries.

Input

The first line contains the integer [latex]n[/latex]. In the second line [latex]n[/latex] integers of the sequence are given. The third line contains the integer [latex]m[/latex]. Then [latex]m[/latex] lines follow, where line [latex]i[/latex] contains two numbers [latex]x_i[/latex] and [latex]y_i[/latex].

Output

Print the results of the [latex]m[/latex] queries, one query per line.

Tests

Input Output
1 3
-1 2 3
1
1 2
2
2 5
1 2 3 4 5
1
1 5
15
3 5
-1 -2 -3 -4 -5
1
1 5
-1
4 8
1 2 -3 -2 10 1 -15 7
4
1 1
3 4
3 6
1 8
1
-2
11
11
5 9
1 -2 3 -4 5 -6 7 -8 9
3
1 9
2 8
2 4
9
7
3

Algorithm

After analyzing the condition of the problem, we can understand that we need on a given segments of array to find subsegment with a maximum amount. We can solve this task by using segment tree, but before this we should modify it a bit. Create a structure of which our tree consists:

That is, in each vertex of tree we store [latex]4[/latex] values:
  • the answer to the task for the current subsegment
  • the maximum amount among all prefixes
  • the maximum amount among all suffixes
  • the sum on the segment

First we need to get the values in the leaves. It’s simple enough all [latex]4[/latex] fields take the value of the number, that corresponds to this leaf. Now, having values in the leaves, we need to learn how to get the values in parent. For this we use the function Node mergeNodes(Node leftChild, Node rightChild), which assign to parent’s fields such values:

  • Answer in the parent equal to the answer in the right or the left child (means that the best subsegment of the current node is entirely in the left or right child), or the maximum amount of the maximum suffix in the left child and the maximum prefix in the right child (which means that it is partially is in the left child and partially is in the right child).
  • The maximum amount of the parent on prefix is equal to the maximum prefix of left child or sum on segment of left child and maximum prefix of right child.
  • The maximum amount of the parent on suffix is equal to the maximum suffix of right child or sum on segment of right child and maximum suffix of right child.
  • Amount on segment of the parent is equal to the sum on segment of left child and sum on segment of right child.

Now, with all the auxiliary functions for working with a built data structure, we need only to construct a tree and learn to get an answer on it.
We need two more functions:

  • void build(int *base, Node *tree, int currentNode, int left, int right) — recursive construction of a tree from the leaves to the root by initial sequence numbers.
  • Node answer(Node *tree, int currentNode, int left, int right, int leftBorder, int rightBorder) — as in the usual tree segments we get an answer going down by the tree, but instead of any associative function (eg sum or maximum) we execute the merger of nodes described earlier. Resulting node will store an answer corresponding to a given in the query segment.

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.

Code

Links

AL16

Algolist. Data structures. Task 16.

There is a Ministry, that includes [latex]N[/latex] officials ([latex]N[/latex] is a natural number). Each official possibly has subordinates and chiefs. What is more, there are some rules:

  • Subordinates of my subordinate are my subordinates.
  • Chiefs of my chief — my chiefs.
  • My chief is not my subordinate.
  • Each official has no more than one direct chief.

In order to get a license for the export of copper, necessary to obtain a signature of the 1st official — сhief of all the сhiefs. But the situation complicated by the fact, that each official, generally speaking, can require «visas» — signatures some of his immediate subordinates and a bribe — a certain amount of dollars. Non-empty list of possible visas and corresponding to this list bribe are known for each official. The empty list means that the official doesn’t require a visa in this case. The official will put his signature, only if he receives all signatures from one of the visas list and the appropriate bribe.

You need to define and output the permissible and minimal for sum of bribes order and its cost.

Input

The input data is the following sequence of lines:

  • Quantity of officials [latex]N[/latex] ([latex]N < 100[/latex] ).
  • List of subordinates for current visa, which consists of their indeces, suitable to the order in which they came to input (could be empty, it suggests that the official doesn’t require a visa in this case).
  • «bribe» — signalyze, that input of current visa end. In next line you will recieve the cost of bribe — real number [latex]B[/latex] ([latex]0 < B < 10^6[/latex]) .
  • «next_official» — determine that information about previous official ended and next line will contain empty or not empty list of next official’s visas (there is no such command before 1st official. If there is no command «next_official « after the number, that determine a bribe, you will recieve next visa of the current official).

More info about input data you can find in test examples.

Output

You need to output in the separate lines the minimum sum of bribes for getting a license and the order. This is a string with the consecutive indices of the officials, who participated in the payment of the minimum bribe, (in order of raising in the hierarchical system, from left to right (arranging in entering the appropriate official)) separated with delimetr /.

Tests

Input Output
1 2
2
bribe
50
next_official
50
2/1
2 5
2
bribe
100
3
bribe
200
4
bribe
150
next_official
5
bribe
10
next_official
next_official
next_official
110
5/2/1
3 7
2
bribe
150
3
bribe
50
next_official
4
bribe
40
5
bribe
20
next_official
6
bribe
150
7
bribe
200
next_official
next_official
next_official
next_official
170
5/2/1
4 5
2
bribe
50
next_official
3
bribe
40
4
bribe
10
next_official
next_official
5
bribe
10
next_official
70
5/4/2/1
5 8
2
bribe
100
next_official
3
bribe
200
4
bribe
150
3 4
bribe
50
next_official
7
bribe
25
next_official
5
bribe
10
6
bribe
80
next_official
next_official
next_official
8
bribe
35
next_official
220
8/7/5/3/4/2/1

tree_2

Illustration for the test №3tree_1Illustration for the test №4

treeIllustration for the test №5

Algorithm

In order to implement solution of this problem, we construct two data structures Visa and Official. First of these stores fields vector <unsigned int> listOfSubordinatesForBribe — indices of subordinates, whose signatures are needed in this bribe and directly bribe. Every official, in their turn, has Id (serial number) and a list of all his visas — vector <Visa> listOfRequiredVisas. Also, we need two functions:

    • bool isBypassed(Official currentOfficial, string order) — determines whether the official is bypassed. It is realized on the condition that every official has no more than one direct chief. Therefore to find out if we take into account this official, we need to check whether there is in the list of bypassed at least one of his subordinates. Implementing a check directly on the current official Id is not possible, because we will go recursively from the leaves to the root.
    • void findCheapestWay(Official *listOfOfficials, Official currentOfficial, string &amp;order, unsigned int &amp;minimumBribe) — the main function dedicated to the search of the answer. Consider its job in detail:
      Because there is no point in considering the officials, who don’t require any visa, we will process only those,who have non-empty list of visas and haven’t been visited yet. Otherwise, we will just go up to a higher level in the tree. For each official store vector <unsigned int> possibleSumsOfBribes and vector <string> possibleOrdersOfBypassing — possible variants of bribes and the order by which it was achieved. Also, we need two variables passed by reference in function — number minimumBribe and string order. They will help us to maintain a minimum bribe and its order at each hierarchy level, when we will call the recursive search for each subordinate in the visa.

Let us turn to the main executable part of the program. Organize the correct reading of the incoming data stream and save each official with its corresponding Id.
Start the search function of the first and the most important official — root. Getting in the first visa and starting a recursive search for all the subordinates we descend directly to the leaves of the tree. Leaning into a dead end, we start to climb from the bottom up, and for each official we find minimum possible bribe and order directly at his level. Thus we will be able consistently for each branch find it mimimum and pick it up by going to the root of the tree. Doing this for every possible visas, we fill the vector of potential bribes values, in which by searching the minimum element  we can select required value. This will be the lowest possible price for a license.
Further details of the implementation can be seen in the comments to the code.

Code

Code of the program (here you can analyze the working time of program)