| | | |
|
Подстроки подпоследовательностей
Динамическое программирование: один параметр
Динамическое программирование
Дерево отрезков, RSQ, RMQ
Дерево Фенвика
Назовем подпоследовательностью массива a непустой массив b такой, что он может быть получен из массива a удалением нескольких (возможно, никаких) элементов массива a. Например, массив [1,3] является попоследовательностью массива [1,2,3] , но [3,1] не является.
Назовем подотрезком массива a непустой массив b такой, что он может быть получен путем удаления нескольких (возможно, никаких) первых и последних элементов массива a. Например, [1,2] является подотрезком массива [1,2,3] , а [1,3] не является. Несложно заметить, что у массива длины n ровно \( {n(n+1) \over 2}\) подотрезков.
Назовем массив a длины n возрастающим , если для любого 1 ≤ i ≤ n выполняется ai ≤ ai+1.
Монотонностью массива назовем количество его возрастающих подотрезков.
Дан массив a длины n. Посчитайте сумму монотонностей по всем его подпоследовательностям. Так как ответ может быть очень большим, выведите его по модулю 109+7.
Входные данные
В первой строке задано целое число n (1 ≤ n ≤ 200000) — длина массива a.
Во второй строке заданы n целых чисел (1 ≤ ai ≤ 200000) — элементы массива a.
Выходные данные
Выведите одно целое число — сумму монотонностей всех подпоследовательностей по модулю 109+7.
Примечание
В первом тестовом примере у массива есть 7 подпоследовательностей:
- У массива [1] есть ровно один подотрезок и он является возрастающим.
- У массива [2] есть ровно один подотрезок и он является возрастающим.
- У массива [3] есть ровно один подотрезок и он является возрастающим.
- У массива [1,2] есть три подотрезка ([1], [2], [1,2] ) и все они являются возрастающими.
- У массива [1,3] есть три подотрезка ([1], [3], [1,3] ) и все они являются возрастающими.
- У массива [3,2] есть три подотрезка ([3], [2], [3, 2] ), но только два из них ([3] и [2] ) являются возрастающими.
- У массива [1,3,2] есть шесть подотрезков ([1], [3], [2], [1,3], [3,2], [1,3,2] ) и четыре из них ([1], [3], [2], [1,3] ) являются возрастающими.
Во втором тестовом примере все возрастающие подотрезки всех подпоследовательностей имеют длину 1.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
3
1 3 2 |
15 |
| 2 |
3
6 6 6 |
12 |
| |
![]()
|
|
Load Balancing
Дерево Фенвика
Дерево отрезков, RSQ, RMQ
Структуры данных
Тернарный поиск
Коровы Фермера Джона стоят в различных точках (x1,y1)…(xn,yn) его поля (1≤N≤100,000, все xi и yi - положительные нечётные целые числа, не превышающие 1,000,000. ФД хочет разделить своё поле изгородью бесконечной длины с севера на юг, описываемой уравнением x=a (a - чётное целое, так обеспечивается, что изгородь не пройдёт через позицию ни одной коровы). Также он хочет построить изгородь бесконечной длины с востока на запад, которая описывается уравнением y=b, где b - чётное целое. Эти две изгороди пересекаются в точке (a,b), и вместе делят поле на четыре региона.
ФД хочет выбрать a и b так, чтобы получить "сбалансированное" количество коров во всех регионах, т.е. чтобы не было региона, который содержит слишком много коров. Пусть M - максимальное количество коров в этих четырёх регионах, ФД хочет, чтобы M было как можно меньше. Помогите ФД определить это минимально возможное значение для M.
ФОРМАТ ВВОДА:
Первая строка ввода содержит одно целое число, N. Каждая из следующих n строк содержит местоположение одной коровы, указанное её координатами x и y.
ФОРМАТ ВЫВОДА:
Выведите минимально возможное значение M, которое может достичь ФД оптимальным расположением изгородей.
| Ввод |
Вывод |
|
7
7 3
5 5
7 13
3 1
11 7
5 3
9 1
|
2 |
| |
![]()
|
|
Дерево Фенвика
Дерево Фенвика
реализация
Дерево Фенвика − это структура данных, эффективно поддерживающая запросы о сумме префикса числового массива. Для числа t обозначим h(t) максимальное значение k, такое что t делится на 2k. Например, h(24)=3, h(5)=0. Обозначим l(t)=2h(t), например, l(24)=8, l(5)=1.
Рассмотрим массив a[1], a[2], … , a[n] целых чисел. Дерево Фенвика для этого массива — это массив b[1], b[2], …, b[n], такой что \( \sum\limits_{j=i-l(i)+1}^{i}a[j] \) Таким образом: b[1]=a[l], b[2]=a[l]+a[2], b[3]=a[3], b[4]=a[l]+a[2]+a[3]+a[4], b[5]=a[5], b[6]=a[5]+a[6], Например, дерево Фенвика для массива a=(3,−1,4,1,−5,9) есть массив b=(3,2,4,7,−5,4).
Назовем массив само-фенвиковским, если он совпадает со своим деровом Фенвика. Напрмер, массив a=(0,−1,1,1,0,9) таковым является.
Вам дан массив а. Вам разрешается заменять в нем некоторые элементы, не меняя их порядка, чтобы сделать из исходного массива само-фенвиковский. Количество изменений при этом должно быть минимально возможным.
Входные данные
В первой строке входных данных содержится количество чисел в массиве n (1 ≤ n ≤ 100000). Во второй строке находятся сами n целых чисел. Все числа по модулю не превосходят 109.
Выходные данные
Выведите n чисел − элементы видоизмененного массива. Если решений несколько − выведите любое из них.
| |
![]()
|