e-olymp 5274. Фенечка

Задача

Саша находится в процессе творческого поиска. Она хочет сплести ещё одну фенечку, но испытывает сложности при выборе цветов. Сейчас все $n$ ниток, которые она планирует использовать для плетения, выложены в ряд. В процессе размышления Саша время от времени заменяет нитку одного цвета ниткой другого, а также для проверки того, что узор получается тем, который подразумевается, проверяет, что некоторые последовательности цветов ниток равны.

Напишите программу, которая автоматизирует эти проверки.

Входные данные

В первой строке записаны два целых числа $n$ и $k$ — количество ниток в фенечке и запросов к программе, соответственно $(1 \leq n, k \leq 100000).$ Во второй строке записана строка из $n$ символов — цвета ниток в начальном состоянии. Каждый цвет обозначается строчной или прописной буквой латинского алфавита или цифрой. В следующих $k$ строках заданы запросы двух видов:

«* i c» — заменить нитку с номером $i$ на нитку цвета $c$,
«? i j len» — проверить, равны ли последовательности цветов ниток, начинающиеся в позициях $i$ и $j$ и имеющие длину $len$.

Выходные данные

Для каждого запроса второго вида выведите «+», если последовательности равны, или «-« в противном случае.

Тесты

Входные данные Выходные данные
6 3
abccba
? 2 4 2
* 4 a
? 1 4 2
-+
7 4
abacaba
? 1 5 3
* 6 c
? 2 6 2
? 3 5 3
+-+
8 3
atgthcta
? 2 4 3
* 8 h
? 4 7 2
-+
9 3
abbababba
? 1 6 4
* 2 c
? 1 6 4
+-

Код программы

Решение задачи

Наивный алгоритм тратит на выполнение первого запроса $O\left(1\right)$ единиц времени, а на выполнение запросов второго типа — $O\left(n\right)$ единиц времени. Таким образом получаем ассиптотическую временную сложность $O\left(kn\right),$ из-за чего задача не проходит по времени.
Для сравнения строк будем использовать полиномиальный хеш, зависящий от $p$ (в нашем случае $p = 61$), при этом будем отождествлять равенство хешей по модулю $m$ (в нашем случае $m = 2^{64}$) и самих строк (при этом может случиться так, что хеши будут совпадать, а сами строки — нет, но вероятность достаточно мала и мы будем ею пренебрегать). Таким образом мы получаем возможность сравнивать строки за $O\left(1\right)$ единиц времени. Будем использовать для хранения текущего состояния строки (а точнее ее хеша) дерево отрезков, при этом на нижнем ярусе будем хранить хеши каждого отдельного символа строки с учетом его месторасположения в строке. Таким образом получим возможность выполнять запросы и первого, и второго типов за $O\left(\log{n}\right)$ единиц времени, при этом следует учесть, что хеши двух одинаковых подстрок будут отличаться в $p^{j-i} \mod m$ раз, где $i$ — меньший из индексов начала сравниваемых подстрок, $j$ — больший. Таким образом, получаем итоговую асимптотическую сложность алгоритма $O\left(k\log{n}\right)$

Ссылки

Условие задачи на e-olymp
Решение на e-olymp
Код решения на Ideone

e-olymp4491 Трое из Простоквашино

Условие задачи:
— Дядя Федор, Дядя Федор, я научился строить дерево отрезков.
— Подожди, Шарик, я занят.
— Ну Дядя Федор, ну смотри какой я код написал:

— Ну хорошо, Шарик, раз ты так хорошо разобрался с этой темой, давай я тебе дам массив из [latex]n[/latex] неотрицательных чисел и число [latex]k[/latex], а ты мне скажешь сколько существует таких пар [latex]l;r \left ( 1\leq l\leq r\leq n \right ),[/latex] что функция, вызванная следующим образом:

[latex]get[/latex]_[latex]max(1, 1, n, l, r)[/latex]

вернет значение равное [latex]k[/latex]. Можно считать, что перед этим была вызвана функция

[latex]build(1, 1, n)[/latex]

— Хорошо, Дядя Федор!

Входные данные:
В первой строке находятся число [latex]n \left ( 1\leq n\leq 10^{6} \right )[/latex] — количество элементов в массиве и [latex]k \left ( 1\leq k\leq 10^{9} \right )[/latex] — значение, которое должна вернуть функция. В следующей строке находится [latex]n[/latex] неотрицательных чисел, не превышающих [latex]10^{9}[/latex] — элементы массива.

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

Тесты:

Входные данные Выходные данные
[latex]n[/latex] [latex]k[/latex] [latex]elem[/latex]_[latex]tree[][/latex] [latex]ans[/latex]
5 3 1 2 3 2 3 11
10 6 1 4 7 6 2 4 1 9 6 6 7
20 15 5 2 4 7 15 3 15 20 31 15 15 1 23 4 8 15 1 2 15 6 43

Код программы:

Алгоритм решения:
Зададим отрезок массива, на котором обозначим границы [latex]\left [ left, right \right ][/latex]. Инициализируем изначально оба конца нулем. Рассмотрим некоторое [latex]elem\_tree\left [ i \right ][/latex] на нашем сегменте. Тогда если [latex]elem\_tree\left [ i \right ]=k[/latex], то на всем отрезке от [latex]left[/latex] до [latex]i[/latex] максимумом будет [latex]k[/latex]. Увеличим в таком случае [latex]left[/latex] и сделаем его равным [latex]i[/latex], причем [latex]right=0.[/latex] Если [latex]elem\_tree\left [ i \right ]\lt k[/latex], максимум будет также равен [latex]k[/latex]. В таком случае увеличиваем только [latex]right.[/latex] Если же [latex]elem\_tree\left [ i \right ]\gt k[/latex] , то [latex]left[/latex] устанавливаем равным [latex]i+1[/latex], а [latex]right[/latex] обнуляем.
Пройдя по всему массиву, мы должны получить значения [latex]left[/latex] равное количеству пар в которых максимум равен [latex]k[/latex], а [latex]right[/latex] должно стать равным нулю.

Код программы на Java
Условие задачи