Структуры данных

Вам дан массив целых чисел А длиной n.
Необходимо ответить на m запросов вида "сообщите количество различных чисел подотрезка массива А от элемента с индексом l до элемента с индексом r" (обе границы подотрезка включены, массив нумеруется с единицы).

Входные данные:
В первой строке дано два числа: n - количество элементов массива и m - количество запросов (1 <= n, m <= 10⁵).
Во второй строке дано n целых чисел A_i - элементы массива (0 <= A_i <= 10⁶).
Далее дано m строк, в каждой по два числа l и r - границы подотрезка для каждого запроса (1 <= l <= r <= n).

Выходные данные:
В единственной строке выведите через пробел m чисел - для каждого запроса количестве различных чисел на соответствующем подотрезке.

Пример:
 

Входные данные	Выходные данные
7 5 1 3 1 2 2 4 1 1 3 4 5 3 7 2 4 7 7	2 1 3 3 1

На одном из телеканалов каждую неделю проводится следующая лотерея. В течение недели участники делают свои ставки. Каждая ставка заключается в назывании какого-либо M-значного числа в системе счисления с основанием K (то есть, по сути, каждый участник называет M цифр, каждая из которых лежит в диапазоне от 0 до K−1). Ведущие нули в числах допускаются.

В некоторый момент прием ставок на текущий розыгрыш завершается, и после этого ведущий в телеэфире называет выигравшее число (это также M-значное число в K-ичной системе счисления). После этого те телезрители, у кого первая цифра их числа совпала с первой цифрой числа, названного ведущим, получают выигрыш в размере A₁ рублей. Те, у кого совпали первые две цифры числа — получают A₂ рублей (при этом если у игрока совпала вторая цифра, но не совпала первая, он не получает ничего). Аналогично угадавшие первые три цифры получают A₃ рублей. И так далее. Угадавшие все число полностью получают Am рублей. При этом если игрок угадал t первых цифр, то он получает A_t рублей, но не получает призы за угадывание t−1, t−2 и т.д. цифр. Если игрок не угадал первую цифру, он не получает ничего.

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

Входные данные
В первой строке задаются числа N (количество телезрителей, сделавших свои ставки, 1 ≤ N ≤ 100000), M (длина чисел 1 ≤ M ≤ 10) K (основание системы счисления 2 ≤ K ≤ 10). В следующей строке записаны M чисел A₁, A₂, ..., A_M, задающих выигрыши в случае совпадения только первой, первых двух,... , всех цифр (1 ≤ A₁ ≤ A₂ ≤ ... ≤ A_M ≤ 100000). В каждой из следующих N строк записано по одному M-значному K-ичному числу. Числа идут в порядке неубывания.

Выходные данные
В первой строке выведите искомое число (если решений несколько — выведите любое из них), а во второй строке — сумму, которую при назывании телеведущей первого числа придется выплатить в качестве выигрыша.

Примеры

№	Входные данные	Выходные данные
1	10 3 2 1 3 100 000 000 001 010 100 100 100 100 110 111	011 6
2	1 1 10 100 0	1 0

Код Эвана содержит n переменных. Каждая переменная имеет уникальное имя, состоящее только из английских строчных (маленьких) букв. Однажды Эван решил укоротить свой код.

Он хочет заменить имя каждой переменной его непустым префиксом таким образом, что новые имена останутся попарно различными (но новое имя какой-либо переменной может совпадать со старым именем этой или другой переменной). Среди всех таких возможных замен он хочет найти такую, для которой суммарная длина названий переменных будет минимальной.

Строка a является префиксом строки b, если вы можете удалить несколько (возможно, ни одного) символа с конца строки b и получить a.

Найдите минимальную возможную суммарную длину новых имён.

Входные данные:
В первой строке содержится одно целое число n (1 ≤ n ≤ 10⁵) — число переменных в коде Эвана.

Следующие n строк содержат названия переменных по одному на строку. Каждое название не является пустой строкой и содержит только лишь строчные (маленькие) английские буквы. Суммарная длина всех этих строк не больше 10⁵. Все названия переменных различны.

Выходные данные:
Выведите одно целое число — минимально возможную суммарную длину новых названий переменных.

Примеры:
 

Входные данные	Выходные данные
3 codeforces codehorses code	6
5 abba abb ab aa aacada	11
3 telegram digital resistance	3

Пояснения:
В первом примере одним из наилучших вариантов будет сокращение имён в порядке их ввода до "cod", "co", "c".
Во втором примере можно укоротить последнее имя до "aac" и первое имя до "a" без изменения других имён переменных.

У вас есть q запросов и мультимножество A, изначально содержащее только число 0. Запросы бывают трёх видов:

• + x — добавить в мультимножество A число x.
• - x — удалить одно вхождение числа x из мультимножества A. Гарантируется, что хотя бы одно число x в этот момент присутствует в мультимножестве.
• ? x — вам даётся число x, требуется вычислить максимальное значение побитового исключающего ИЛИ (также известно как XOR) числа x и какого-нибудь числа y из мультимножества A.

Мультимножество — это множество, в котором разрешается несколько одинаковых элементов.

Входные данные:
В первой строке входных данных содержится число q (1 ≤ q ≤ 200000) — количество запросов, которые требуется обработать Василию.

Каждая из последующих q строк входных данных содержит один трёх символов «+», «-» или «?» и число x_i (1 ≤ x_i ≤ 10⁹). Гарантируется, что во входных данных встречается хотя бы один запрос «?».

Обратите внимание, что число 0 всегда будет присутствовать в мультимножестве.

Выходные данные:
На каждый запрос типа «?» выведите единственное целое число — максимальное значение побитового исключающего ИЛИ для числа x_i и какого-либо числа из мультимножества A.

Пример:
 

Входные данные	Выходные данные
10 + 8 + 9 + 11 + 6 + 1 ? 3 - 8 ? 3 ? 8 ? 11	11 10 14 13

Есть набор строк, который изначально пуст. Необходимо обрабатывать три различные операции над этим набором строк:

• 1 s: Добавить данную строку в набор.
• 2 k l: Узнать, существуют ли в наборе k строк (не обязательно различных) таких, что они имеют общий суффикс длины l. Этот суффикс не обязан быть наибольшим.
• 3 i: Удалить строку из набора, которая была добавлена в i-й операции (если она еще не была удалена).

Входные данные:
В первой строке дано одно целое число - количество операций q (1 <= q <= 10⁵), которые необходимо обработать.
Далее в каждой строке дано описание запроса. Сперва это число 1, 2 или 3, обозначающее тип запроса. 
Если это запрос первого типа, то далее дана строка s, суммарная длина которых не превышает 10⁵.
Если это запрос второго типа, то далее дано два целых числа k и l (1 <= k, l <= 10⁵).
Если это запрос третьего типа, то далее дано число i (1 <= i <= номер текущей операции), где i - номер операции первого типа.

Выходные данные:
Для каждого запроса второго типа выведите в отдельной строке слово "YES", если существуют необходимые строки, и "NO" в противном случае.

Пример:
 

Входные данные	Выходные данные
9 1 aba 1 accba 2 2 2 2 2 3 1 aaaa 1 ababa 2 3 2 3 1 2 3 2	YES NO YES NO

Дана игра для двоих игроков со строками.

Задан набор, состоящий из n непустых строк. Во время игры два игрока вместе строят слово, изначально это слово пустое. Игроки ходят по очереди. За свой ход игрок должен дописать в конец слова одну букву так, чтобы полученное слово было префиксом хотя бы одной строки из заданного набора. Проигрывает тот, кто не может сделать ход.

По задданому набору строк определите, кто будет победителем, если оба игрока будут играть оптимально.

Входные данные:
Первая строка содержит целое число n (1 ≤ n ≤ 10⁵).
Каждая из n следующих строк содержит непустую строку из заданного набора. Суммарная длина всех строк из набора не превышает 10⁵. Все строки из набора состоят только из строчных латинских букв.

Выходные данные:
Если победит игрок, который ходит первым, то выведите «First», иначе выведите «Second» (кавычки выводить не нужно).

Примеры:
 

Входные данные	Выходные данные
3 a b c	First
1 ab	Second

Вам даны N целых чисел A1, ..., AN.
На каждый из Q запросов, заданных в формате L R X, выведите количество элементов среди AL, ..., AR, значения которых равны X.

Входные данные
В первой строке задано целое число N (1 <= N <= 2·10⁵). 
Вторая строка содержит N целых чисел Ai (1 <= A_i <= N, 1 <= i <= N). 
В третьей строке задано одно целое число Q (1 <= Q <= 2·10⁵).
Каждая из следующих Q строк содержит три целых числа L, R, X (1 <= L <= R <= N, 1 <= X <= N).

Выходные данные
Выведите на экран Q строк, i-я строка содержит ответ на i-й запрос.
 

Примеры

№	Входные данные	Выходные данные
1	5 3 1 4 1 5 4 1 5 1 2 4 3 1 5 2 1 3 3	2 0 0 1

У Макс в блокноте были записаны две строки s длины n и t длины m, состоящие из букв «a» и «b» латинского алфавита. Причем Макс знает, что строка t имеет вид «abab...», то есть на нечетных позициях строки стоит буква «a», а на четных — «b».

Вдруг утром Макс обнаружила, что кто-то испортил ее строку s. Некоторые буквы s были заменены на символ «?».

Назовем последовательность позиций i, i + 1, ..., i + m - 1 вхождением строки t в s, если 1 ≤ i ≤ n - m + 1 и t₁ = s_i, t₂ = s_i + 1, ..., t_m = s_{i + m - 1}.

Красота строки s оценивается как максимальное количество непересекающихся вхождений строки t в нее. Макс может заменить некоторые из символов «?» на «a» или «b» (символы на разных позициях можно заменять на разные буквы). Макс хочет произвести замены так, чтобы красота строки s была максимально возможной. Из всех таких вариантов она хочет заменить как можно меньше символов «?». Найдите, сколько замен она должна сделать.

Входные данные:
Первая строка содержит одно целое число n (1 ≤ n ≤ 10⁵) — длину строки s.
Вторая строка входных данных содержит строку s длины n, состоящую только из букв «a» и «b» латинского алфавита, а также символов «?».
Третья строка содержит целое число m (1 ≤ m ≤ 10⁵) — длину строки t. Сама строка t содержит «a» на нечетных позициях, и «b» на четных.

Выходные данные:
Выведите единственное целое число — минимальное количество замен, которое должен сделать Вася, чтобы сделать красоту строки s максимально возможной.

Примеры:
 

Входные данные	Выходные данные
5 bb?a? 1	2
9 ab??ab??? 3	2

Пояснения:
В первом примере строка t имеет вид «a». Единственный оптимальный вариант — заменить все символы «?» на «a».
Во втором примере используя две замены можно получить строку «aba?aba??». Больше двух вхождений получить нельзя.

Вам дан массив из n целых чисел. Вам необходимо разделить его на k непустых подотрезков (последовательность подряд идущих элементов) так, чтобы:
1) Каждый элемент массива входил ровно в один подотрезок.
2) Если для каждого подотрезка выбрать минимальное в нем число, то сумма всех минимумов должна быть максимально возможной.

Сообщите сумму минимумов значений в подотрезках этого разбиения.

Входные данные:
В первой строке дается два натуральных числа - n (1 <= n <= 500) и k (1 <= k <= n).
Во второй строке дается n целых чисел - элементы массива a_i (1 <= a_i <= 10⁵).

Выходные данные:
Выведите одно число - ответ на задачу.

Пример:
 

Входные данные	Выходные данные
5 3 4 2 5 1 3	8

Пояснение:
Одно из подходящих разбиений: [4, 2], [5], [1, 3]. Сумма минимумов в каждом подотрезке равна 2 + 5 + 1 = 8.

Дочь короля Флатландии собирается выйти за прекрасного принца. 
Принц хочет подарить принцессе сокровища, но он не уверен какие именно бриллианты из своей коллекции выбрать.

В коллекции принца n бриллиантов, каждый характеризуется весом w_i и стоимостью v_i. 
Принц хочет подарить наиболее дорогие бриллианты, однако король умен и не примет бриллиантов суммарного веса больше R. С другой стороны, принц будет считать себя жадным всю оставшуюся жизнь, если подарит бриллиантов суммарным весом меньше L.

Помогите принцу выбрать набор бриллиантов наибольшей суммарной стоимости, чтобы суммарный вес был в отрезке [L, R].

Входные данные:
Первая строка содержит число n (1 <= n <= 32), L и R (0 <= L <= R <= 10¹⁸).
Следующие n строк описывают бриллианты и содержат по два числа - вес и стоимость соответствующего бриллианта (1 <= wi, vi <= 10¹⁵).

Выходные данные:
Первая строка вывода должна содержать k - количество бриллиантов, которые нужно подарить принцессе. 
Вторая строка должна содержать номера даримых бриллиантов.
Бриллианты нумеруются от 1 до n в порядке появление во входных данных.

Если составить подарок принцессе невозможно, то выведите 0 в первой строке вывода.

Примеры:
 

Входные данные	Выходные данные
3 6 8 3 10 7 3 8 2	1 2

Петя и Вася с упоением играют в шпионов. Сегодня они планируют, где будут 
расположены их секретные бункеры и штаб-квартира. 

Пока Петя и Вася решили, что им понадобится ровно n бункеров, которые для секретности будут пронумерованы числами от 1 до n. 
Некоторые из них будут соединены двусторонними тоннелями, причем для надежности и секретности по тоннелям можно будет попасть из любого бункера в любой единственным образом.
Петя и Вася даже решили, какие из бункеров будут соединены тоннелями, но выбрать, какой из них будет штаб-квартирой, они не могут. 
Мальчики хотят выбрать ее и разделить оставшиеся бункеры между собой таким образом, чтобы им досталось поровну бункеров к штаб-квартире вело бы ровно два тоннеля: один от бункера, принадлежащего Васе, другой - от бункера, принадлежащего Пете. 
                                                                                   
Уставший Петя пошел к себе домой, а утром Вася показал ему план, на котором бункеры были обозначены точками, а тоннели отрезками. 
Кроме того, Вася выбрал штаб-квартиру таким образом, что нарисованный им план был симметричен относительно прямой, проходящей через точку, которая соответствовала штаб-квартире.
 
Хотя Петя почти сразу показал Васе, что тот ошибся и не нарисовал половину бункеров, ему стало интересно, можно ли выбрать штаб-квартиру и нарисовать такой симметричный план.

Входные данные:
В первой строке входного файла находится одно целое число n (1 <= n <= 10⁵) - количество бункеров. 
В следующих n - 1 строках находится по два целых числа u_i и v_i (1 <= u_i, v_i <= n, u_i ≠ v_i) - номера бункеров, которые соединяет i-ый тоннель. 
Гарантируется, что между любыми двумя бункерами существует единственный путь.

Выходные данные:
В выходной файл выведите "YES", если можно выбрать штаб-квартиру и нарисовать такой план, или "NO" если это невозможно.

Примеры:
 

Входные данные	Выходные данные
2 1 2	NO
3 1 2 2 3	YES

Вам дано t запросов, в каждом из которых вам дана строка s, состоящая из строчных латинских букв, число p и число mod.
Для каждого запроса вычислите полиномиальный хэш с основанием p по модулю mod от строки, являющейся строкой s, где каждая буква продублирована. То есть, если s = "isaac", то нужно посчитать хэш от строки "iissaaaacc".

Входные данные:
В первой строке дается число t - количество запросов.
Далее идет t строк, в каждой из которых через пробел даны s (1 <= |s| <= 20), p (1 <= p <= 10⁵) и mod (1 <= mod <= 10⁸).

Выходные данные:
Выведите ответы на запросы, каждый в отдельной строке.

Пример:
 

Входные данные	Выходные данные
2 isaac 12345 87654321 newton 54321 12345678	8829000 9632318

Дана последовательность из N чисел. Рассматриваются все её непрерывные подпоследовательности, которые содержат кратное K количество отрицательных чисел, заканчивающихся цифрой m. Найдите среди них подпоследовательность с максимальной суммой.  Программа должна вывести одно число – максимальную сумму элементов такой подпоследовательности. Гарантируется, что в исходной последовательности существует хотя бы K отрицательных чисел, заканчивающихся цифрой m.


Входные данные
В первой строке программа получается три числа: количество чисел в последовательности N (100 <= N <= 5000000), натуральное число K и натуральное число m (0 <= m <= 9). В каждой из следующих N строк записано одно целое число, не превышающее по модулю 10000. Гарантируется, что сумма любой подпоследовательности исходной последовательности не превышает по модулю 10⁹.

Выходные данные
Выведите на экран ответ на задачу.
 
 

Примеры

№	Входные данные	Выходные данные	Пояснение
1

 

Дана последовательность из N чисел. Рассматриваются все её непрерывные подпоследовательности, которые содержат ровно K отрицательных чисел, заканчивающихся цифрой m. Найдите среди них подпоследовательность с максимальной суммой.  Программа должна вывести одно число – максимальную сумму элементов такой подпоследовательности. Гарантируется, что в исходной последовательности существует хотя бы K отрицательных чисел, заканчивающихся цифрой m.

Входные данные
В первой строке программа получается три числа: количество чисел в последовательности N (100 <= N <= 5000000), натуральное число K и целое число m (0 <= m <= 9). В каждой из следующих N строк записано одно целое число, не превышающее по модулю 10000. Гарантируется, что сумма любой подпоследовательности исходной последовательности не превышает по модулю 10⁹.

Выходные данные
Выведите на экран ответ на задачу.
 
 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	8 2 3 6 -3 -2 4 -1 -13 8 13	12	Нужные нам числа -3 и -13. Вся исходная последовательность даст максимальную сумму элементов.

На вход программе подается последовательность целых чисел.  Рассматриваются все непрерывные подпоследовательности исходной последовательности, сумма элементов которых кратна K. Найдите количество таких подпоследовательностей. Гарантируется, что в последовательности такая подпоследовательность есть.

Входные данные
В первой строке записаны натуральные числа N (1 <= N <= 10⁸) и K (1 <= K <= 100 ). Каждая из следующих N строк содержит одно натуральное число, не превышающих 10000.

Выходные данные
Выведите на экран одно число – количество таких подпоследовательностей. 

Примеры

№	Входные данные	Выходные данные
1	5 3 33 41 19 22 40	4

Дана последовательность из N чисел. Рассматриваются все её непрерывные подпоследовательности, в которых количество отрицательных чисел не превышает С. Найдите среди них подпоследовательность с максимальной суммой, длины L. В ответе укажите сумму найденной подпоследовательности.

Входные данные
В первой строке записаны 3 числа: количество чисел N (1 <= N <= 1 000 000),  L и C (\(1 <= L, C <= N <= 1 000 000\)). Каждая из следующих N строк содержит одно число, не превышающее по модулю 1 000.

Пример организации исходных данных во входном файле (для L = 3 и С = 3):
5 3 3
1
-1
2
-2
3

В этом наборе можно выбрать несколько последовательностей, но с максимальной суммой равной 3 будет: 2+(-2)+3. 
Ответ (для С = 3 и L = 3): 3. 

 

Дана последовательность из N натуральных чисел. Рассматриваются все её непрерывные подпоследовательности, такие что сумма элементов каждой из них кратна K. Найдите среди них подпоследовательность с максимальной суммой, определите её длину. Если таких подпоследовательностей найдено несколько, в ответе укажите количество элементов самой короткой из них.

Входные данные
В первой строке записаны натуральные числа N (1 <= N <= 10⁸) и K (1 <= K <= 100 ). Каждая из следующих N строк содержит одно натуральное число, не превышающих 10000.

Выходные данные
Выведите на экран одно число - количество элементов самой короткой подпоследовательности с максимальной суммой элементов кратной К.
 
 

Примеры

№	Входные данные	Выходные данные
1	7 43 21 13 9 19 17 26 95	2

В этом наборе можно выбрать последовательности 21+13+9 (сумма 43) и 17+26 (сумма 43). Самая короткая из них, 17 + 26, имеет длину 2. Для указанных программа должна вывести число 2.

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


Входные данные
В первой строке записаны два числа: количество чисел в последовательности N (1 <= N <= 10⁸) и число K (1 <= K <= 100). Далее идет N строк, по одному целому числу в строке. Каждое число не превышает 10000.

Выходные данные
Выведите на экран ответ на задачу.
 
 

Примеры

№	Входные данные	Выходные данные
1	5 2 2 -2 2 -2 2	2

 

 

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


Входные данные
В первой строке записаны два числа: количество чисел в последовательности N (1 <= N <= 10⁸) и число K (1 <= K <= 100). Далее идет N строк, по одному натуральному числу в строке. Каждое число не превышает 10000.

Выходные данные
Выведите на экран ответ на задачу.
 

Примеры

№	Входные данные	Выходные данные
1	5 3 33 41 18 23 40	92

 
 

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

Входные данные
В первой строке записаны два числа: количество чисел в последовательности N (1 <= N <= 10⁸) и число K (1 <= K <= 100). Далее идет N строк, по одному натуральному числу в строке. Каждое число не превышает 10000.

Выходные данные
Выведите на экран ответ на задачу.
 

Примеры

№	Входные данные	Выходные данные
1	5 3 33 41 18 23 40	2