--->
14 задач
<---
Источники
Дан неориентированный граф без петель и кратных ребер, у которого n вершин и m ребер. У каждой вершины есть цвет. Требуется ответить на q запросов. Каждый запрос имеет один из двух типов:
1 v c – перекрасить вершину v в цвет c
2 v – вычислить количество различных цветов у соседей вершины v .
В первой строке даны три целых числа n , m и q ( 1 ≤ n ≤ 10 5 , 1 ≤ m , q ≤ 2·10 5 ).
Во второй строке через пробел даны n целых чисел 1 ≤ c 1 , ..., c n ≤ n – цвета вершин.
В следующих m строках заданы по два целых числа u и v – номера вершин, которые соединяет очередное ребро ( 1 ≤ u , v ≤ n , u ≠ v ).
В следующих q строках заданы запросы. Каждый запрос имеет один из двух типов:
1 v c – перекрасить вершину v в цвет c , 1 ≤ v , c ≤ n .
2 v – вычислить количество различных цветов у соседей вершины v , 1 ≤ v ≤ n .
Для каждого запроса второго типа выведите в отдельной строке ответ на него.
4 3 3 1 2 3 4 1 2 1 3 1 4 2 1 1 4 3 2 1
3 2
Для заданного массива требуется выполнить ряд запросов. Все запросы делятся на два типа. Запрос первого типа – вычислить количество элементов массива на отрезке от l до r меньших заданного числа x . Запрос второго типа – увеличить все элементы массива на отрезке от l до r на заданное число x .
В первой строке заданы два целых числа n и q – размер массива и количество запросов ( 1 ≤ n , q ≤ 2·10 5 ).
Во второй строке через пробел заданы n целых чисел - 10 9 ≤ a 1 , ..., a n ≤ 10 9 – элементы массива.
В следующих q строках содержатся запросы. Каждый из запросов имеет один из двух видов:
1 l r x – запрос количества элементов на отрезке от l до r меньших заданного числа x ( 1 ≤ l ≤ r ≤ n , - 10 9 ≤ x ≤ 10 9 ).
2 l r x – запрос инкремента на величину x на отрезке от l до r ( 1 ≤ l ≤ r ≤ n , - 10 6 ≤ x ≤ 10 6 ).
На каждый запрос первого типа выведите в отдельной строке ответ на этот запрос.
5 3 1 2 3 4 5 1 1 5 5 2 2 4 2 1 1 5 5
4 2
Скажем, что последовательность строк 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
По мнению Александра Павловича, текст необычайно красив, если некоторые особые слова (например, «коммунизм», «Ленин», «счастье») встречаются не слишком часто, но и не слишком редко, к тому же достаточно равномерно.
Александр Павлович работает корректором. К нему поступают тексты, он имеет право их некоторым образом менять, после чего возвращает уже исправленную версию.
В связи со своими воззрениями о красоте Александру Павловичу постоянно приходится проверять, сколько особых слов сейчас в той или иной части текста.
Он настолько устал от рутинного подсчёта: «а сколько тут особых слов?», «а сколько тут?», что просит вас помочь ему автоматизировать этот процесс.
Первая строка входного файла содержит текст длины \(L\) (\(1 \leq L \leq 10^5\)), в котором ищутся особые слова.
Следующая строка содержит \(N\) (\(1 \le n \le 10^5\)) — количество особых слов.
Следующие \(n\) строк содержат особые слова. Все особые слова различны. Суммарная длина строк не превосходит \(10^5\).
В следующей строке дано \(Q\) (\(1 \le q \le 10^5\)) — количество интересных Александру Павловичу отрезков.
Следующие \(q\) строк содержат сами отрезки.
Выведите \(q\) чисел — количества вхождений особых слов в соответствующий отрезок текста.
Тесты к данной задаче состоят из семи групп тестов. Баллы за каждую группу тестов ставятся только при прохождении всех тестов группы и всех тестов зависимых групп и теста из условия.
Обозначим за \(LEN_{max}\) максимальную длину особого слова.
abacababa 2 a aba 3 5 9 2 2 2 6
5 0 2
У Винни-Пуха есть \(n\) бочек меда. В \(i\)-й бочке налито \(a_i\) меда, а объем бочки равен \(b_i\) (\(1 \le i \le n\)). Винни-Пух хочет полностью заполнить все свои бочки. Для этого он последовательно делает \(q\) шагов. На \(j\)-м шаге он будет наливать мед в бочки с номерами от \(l_j\) до \(r_j\) (\(1 \le j \le q\)). В бочку с номером \(l_j\) Винни-Пух нальет \(c_j\) меда, в следующую бочку он нальет \(c_j + d_j\) меда, в следующую \(c_j + 2 \cdot d_j\) меда и так далее до бочки с номером \(r_j\).
Для каждой бочки требуется вывести номер шага, после которого она окажется полностью заполненной. Если после выполнения всех шагов бочка так и не заполнится, то для нее необходимо вывести число 0.
В первой строке даны два целых числа \(n\) и \(q\) (\(1 \le n, \ q \le 2 \cdot 10^5\)).
Во второй строке через пробел даны \(n\) целых чисел \(0 \le a_1, \ldots, a_n \le 10^5\).
В третьей строке через пробел даны \(n\) целых чисел \(1 \le b_1, \ldots, b_n \le 10^9\).
В следующих \(q\) строках даны по четыре целых числа \(l_j\), \(r_j\), \(c_j\), \(d_j\) (\(1 \le l_j \le r_j \le n\), \(0 \le c_j, \ d_j \le 10^5\), \(1 \le j \le q\)).
Гарантируется, что \(a_i < b_i\) для всех \(1 \le i \le n\).
В единственной строке выведите \(n\) целых чисел -- ответ для каждой из бочек.
5 3 0 0 0 0 2 7 7 7 7 7 1 5 1 1 2 5 1 1 1 3 4 0
0 3 3 2 1