Известно, что если сохранить в каждом слове текста первую и последнюю букву, а остальные переставить произвольным образом, получившийся текст по-прежнему можно достаточно свободно прочитать. В лаборатории информатики исследуют аналогичный феномен для числовых последовательностей.
Будем называть последовательность, состоящую из целых положительных чисел, корректной , если первое число в этой последовательности является минимальным, а последнее — максимальным. Например, последовательности [1, 3, 2, 4] и [1, 2, 1, 2] являются корректными, а последовательность [1, 3, 2] — нет.
Задана последовательность [ a 1 , a 2 , ..., a n ] . Будем называть отрезок элементов заданной последовательности [ a l , a l + 1 , ..., a r ] корректным, если он представляет собой корректную последовательность: a l является минимальным числом на этом отрезке, а a r — максимальным.
В рамках исследования необходимо разбить заданную последовательность на минимальное количество непересекающихся корректных отрезков. Например, последовательность [2, 3, 1, 1, 5, 1] можно разбить на три корректных отрезка: [2, 3] и [1, 1, 5] и [1] .
Требуется написать программу, которая по заданной последовательности определяет, на какое минимальное количество корректных отрезков её можно разбить.
Первая строка входных данных содержит целое число n ( 1 ≤ n ≤ 300 000 ) — количество элементов в заданной последовательности.
Вторая строка содержит n целых чисел a 1 , a 2 , ..., a n — заданную последовательность ( 1 ≤ a i ≤ 10 9 ).
Выведите одно число — минимальное количество корректных отрезков, на которое можно разбить заданную последовательность.
5 5 4 3 2 1
5
4 1 3 2 4
1
6 2 3 1 1 5 1
3
Скажем, что последовательность строк t 1 , ..., t k является путешествием длины k , если для всех i > 1 t i является подстрокой t i - 1 строго меньшей длины. Например, { ab , b } является путешествием, а { ab , c } или { a , a } — нет.
Определим путешествие по строке s как путешествие t 1 , ..., t k , все строки которого могут быть вложены в s так, чтобы существовали (возможно, пустые) строки u 1 , ..., u k + 1 , такие, что s = u 1 t 1 u 2 t 2 ... u k t k u k + 1 . К примеру, { ab , b } является путешествием по строке для abb , но не для bab , так как соответствующие подстроки расположены справа налево.
Назовём длиной путешествия количество строк, из которых оно состоит. Определите максимально возможную длину путешествия по заданной строке s .
В первой строке задано целое число n ( 1 ≤ n ≤ 500 000 ) — длина строки s .
Во второй строке содержится строка s , состоящая из n строчных английских букв.
Выведите одно число — наибольшую длину путешествия по строке s .
В первом примере путешествием по строке наибольшей длины является { abcd , bc , c } .
Во втором примере подходящим вариантом будет { bb , b } .
7 abcdbcc
3
4 bbcb
2
Назовем подпоследовательностью массива \(a\) непустой массив \(b\) такой, что он может быть получен из массива \(a\) удалением нескольких (возможно, никаких) элементов массива \(a\). Например, массив \([1, 3]\) является попоследовательностью массива \([1, 2, 3]\), но \([3, 1]\) не является.
Назовем подотрезком массива \(a\) непустой массив \(b\) такой, что он может быть получен путем удаления нескольких (возможно, никаких) первых и последних элементов массива \(a\). Например, \([1, 2]\) является подотрезком массива \([1, 2, 3]\), а \([1, 3]\) не является. Несложно заметить, что у массива длины \(n\) ровно \(\frac{n(n + 1)}{2}\) подотрезков.
Назовем массив \(a\) длины \(n\) возрастающим , если для любого \(1 \leq i < n\) выполняется \(a_i < a_{i + 1}\).
Монотонностью массива назовем количество его возрастающих подотрезков.
Дан массив \(a\) длины \(n\). Посчитайте сумму монотонностей по всем его подпоследовательностям. Так как ответ может быть очень большим, выведите его по модулю \(10^9 + 7\).
В первой строке задано целое число \(n\) (\(1 \leq n \leq 200\,000\)) — длина массива \(a\).
Во второй строке заданы \(n\) целых чисел (\(1 \leq a_i \leq 200\,000\)) — элементы массива \(a\).
Выведите одно целое число — сумму монотонностей всех подпоследовательностей по модулю \(10^9 + 7\).
В первом тестовом примере у массива есть \(7\) подпоследовательностей:
Во втором тестовом примере все возрастающие подотрезки всех подпоследовательностей имеют длину \(1\).
3 1 3 2
15
3 6 6 6
12
Члены комиссии соревнования ICPC не смогли придумать задачи, поэтому они решили ранжировать команды лексикографически. Таким образом, победителем станет команда, название которой лексикографически самое маленькое. Героиня этой задачи, Этна, является лидером команды, личность которой мы будем скрывать. Название её команды начинается с буквы «Z», что ставит её в довольно плохое положение. После долгих разговоров с комитетом Этна смогла добиться более справедливого способа ранжирования команд. К сожалению, команды будут продолжать сортировать лексикографически, но определение лексикографического порядка изменится. А именно, комитет случайным образом выберет перестановку букв английского алфавита и определит лексикографический порядок, используя эту перестановку. Этна сразу же достала свой ноутбук и написала программу, которая находит перестановку букв для каждой команды, согласно которой эта команда выиграет соревнование. К сожалению, программа еще не закончена. Помогите Этне и напишите более эффективную программу с той же функциональностью.
На первной строке дано натуральное число \(N\), которое обозначает количество команд, участвующих в соревновании.
В следующих \(N\) строках даны названия команд, участвующих в соревновании. Название каждой команды состоит из одного слова, которое в свою очередь состоит из строчных букв английского алфавита. Конечно, названия команд отличаются друг от друга.
Для каждой команды в исходном порядке необходимо вывести перестановку букв английского алфавита, в соответствии с которой эта команда выиграет соревнование. Если такой перестановки нет, необходимо вывести слово «nemoguce», а если таких перестановок несколько, достаточно вывести любую.
В этой задаче 3 подгруппы. Обозначим \(L\) - суммарную длину строк, \(K\) - количество различных букв.
(13 баллов) \(1 \le N \le 100, 1 \le L \le 10000, 1 \le K \le 6\)
(32 балла) \(1 \le N \le 350, 1 \le L \le 10000, 1 \le K \le 26\)
(55 баллов) \(1 \le N \le 25000, 1 \le L \le 1000000, 1 \le K \le 26\)
3 war zag wro
yxwzvutsqponmlkjihgfedcbar zyxwvutsrqponmlkjihgfedcba yxwzvutsrqponmlkjihgfedcba
3 b ab aa
zyxwvutsrqponmlkjihgfedcba nemoguce zyxwvutsrqponmlkjihgfedcab
7 bcada dbaab bbabc ababb aacdf bcdff baddb
zyxwvutsrqponmlkjihgfecbad zyxwvutsrqponmlkjihgfedcba zyxwvutsrqponmlkjihgfebdca nemoguce zyxwvutsrqponmlkjihgfecadb zyxwvutsrqponmlkjihgfecbda nemoguce
В рамках новой рекламной кампании некоторая корпорация хочет разместить свой логотип где-нибудь в городе. Компания собирается потратить весь рекламный бюджет на логотип, поэтому он должен быть воистину огромным. Один из менеджеров решил использовать здания целиком как части логотипа.
Логотип состоит из \(n\) вертикальных полос различной высоты. Полосы пронумерованы от \(1\) до \(n\) слева направо. Логотип описывается перестановкой \((s_1, s_2, ..., s_n)\) чисел \(1, 2, ..., n\). Полоса с номером \(s_1\) - самая низкая, полоса с номером \(s_2\) - следующая по высоте и, наконец, полоса \(s_n\) - самая высокая. Фактическая высота полос не имеет большого значения. Вдоль главной улицы расположено \(m\) зданий. К вашему удивлению, высота зданий различна. Задача состоит в том, чтобы найти все позиции, на которых логотип соответствует зданиям. Помогите компании и найдите все непрерывные последовательности зданий, которые соответствуют логотипу. Непрерывная последовательность зданий соответствует логотипу, если здание \(s_1\) в этой последовательности является самым низким, здание \(s_2\) является следующим по высоте и т. д. Например, последовательность зданий высотой \(5, 10, 4\) соответствует логотипу, описанному перестановкой \((3, 1, 2)\), поскольку здание №3 (высотой 4) является самым низким, здание №1 - вторым по высоте, а здание №2 - самым высоким.
Первая строка стандартного ввода содержит два целых числа \(n\) и \(m\) \((2 \le n \le m \le 1 000 000)\).
Вторая строка содержит \(n\) целых чисел \(s_i\), образующих перестановку чисел \(1, 2, ..., n\). То есть \(1 \le s_i \le n\) и s\(_i \neq s_j\) для \(i \neq j\).
Третья строка содержит \(m\) целых чисел \(h_i\) - высоты зданий (\(1 \le h_i \le 10^9\) для \(1 \le i \le m\)). Все числа различные.
В каждой строке числа разделены пробелами.
Первая строка стандартного вывода должна содержать целое число \(k\) – количество совпадений.
Вторая строка должна содержать \(k\) целых чисел - индексы зданий начиная с 1, которые соответствуют первой полосе из логотипа в правильном соответствии. Числа должны быть перечислены в возрастающем порядке.
Если \(k = 0\), ваша программа должна напечатать пустую вторую строку.
В тестах суммарной стоимостью не менее 35 баллов \(n \le 5000\) и \(m \le 20 000\).
В тестах суммарной стоимостью не менее 60 баллов \(n \le 50 000\) и \(m \le 200 000\).
5 10 2 1 5 3 4 5 6 3 8 12 7 1 10 11 9
2 2 6