Саша находится в
процессе творческого поиска. Она хочет сплести ещё одну фенечку, но испытывает
сложности при выборе цветов. Сейчас все n
ниток, которые она планирует использовать для плетения, выложены в ряд. В
процессе размышления Саша время от времени заменяет нитку одного цвета ниткой
другого, а также для проверки того, что узор получается тем, который
подразумевается, проверяет, что некоторые последовательности цветов ниток
равны.
Напишите
программу, которая автоматизирует эти проверки.
Вход. В первой строке записаны два целых числа n и k
– количество ниток в фенечке и запросов к программе, соответственно (1 ≤ n, k
≤ 100000). Во второй строке записана строка из n символов – цвета ниток в начальном состоянии. Каждый цвет
обозначается строчной или прописной буквой латинского алфавита или цифрой. В
следующих k строках заданы запросы
двух видов:
"* i c" – заменить нитку с номером i на нитку цвета c,
"? i j len" – проверить, равны ли
последовательности цветов ниток, начинающиеся в позициях i и j и имеющие длину len.
Выход. Для каждого запроса второго вида выведите "+",
если последовательности равны, или "-" в противном случае.
|
Пример
входа |
Пример
выхода |
|
7 4 abacaba ? 1 5 3 * 6 c ? 2 6 2 ? 3 5 3 |
+-+ |
дерево
Фенвика
Пусть в строке S
= s1s2 … sn
находится текущее состояние фенечки. Построим по ней полиномиальный хеш, равный
H(S) = s1 * p +
s2 * p2 + …
+ sn * pn, где p – некоторое простое число, большее количества букв. Возьмем,
например p = 37.
Пусть ячейки
массива m содержат слагаемые хеша так что m[i]
= si * pi. Массив m будем
моделировать при помощи дерева Фенвика. Изначально обнулим массив m, после чего
совершим прибавление Inc(i, si * pi). Для удобства буквы закодируем начиная с 1: букве ‘a’ поставим в сооветствие код 1, букве ‘b’ код 2, и так
далее.
Пусть функция
Sum(i) возвращает сумму s1 * p + s2 * p2 + … + si * pi.
Тогда последовательность цветов ниток, начинающихся в позиции i длины len, имеет хеш si
* pi + si+1 * pi+1 + … + si+len-1 * pi+len-1, равный Sum(i + len
– 1) – Sum(i – 1). А
последовательность цветов ниток, начинающихся в позиции j длины len, имеет хеш sj * pj + sj+1
* pj+1 + … + sj+len-1 * pj+len-1, равный Sum(j + len
– 1) – Sum(j – 1). Подстроки sisi+1…si+len-1 и sjsj+1…sj+len-1 равны, когда их хеши различаются в pj-i
раз (пусть i < j для определенности). Действительно:
(Sum(i + len
– 1) – Sum(i – 1)) * pj-i = si *
pj + si+1 * pj+1
+ … + si+len-1 * pj+len-1
=
(учитывая что si = sj, si+1
= sj+1, …, si+len-1 = sj+len-1) = sj * pj
+ sj+1 * pj+1 + … + sj+len-1 * pj+len-1 =
= Sum(j + len
– 1) – Sum(j – 1)
Все вычисления
проводим в типе данных long long, не обращая внимание на переполнение.
Определим рабочие массивы.
#define MAX 100010
long long
p = 37;
long long
Pow[MAX], Fenwick[MAX];
char s[MAX];
Прибавление mi += delta.
void Inc(int
i, long long
delta)
{
for (; i
<= n; i = (i | (i+1)))
Fenwick[i] += delta;
}
Вычисление суммы m0 + m1
+ ... + mi.
long long
Sum(int i)
{
long long result = 0;
for (; i
>= 0; i = (i & (i + 1)) - 1)
result += Fenwick[i];
return
result;
}
Основная часть программы. Читаем
входные данные. Строку s читаем с
позиции 1, так как индексы в запросах начинаются с 1.
scanf("%d %d\n",&n,&q);
gets(s+1);
Вычисляем степени числа p = 37: Pow[i] = pi. На
переполнение не обращаем внимание.
Pow[0] = 1;
for(i = 1; i <= n; i++)
Pow[i] = p * Pow[i - 1];
Совершаем присваивание m[i] = si
* pi, массив m моделируем деревом Фенвика.
for(i = 1; i <= n; i++)
Inc(i, Pow[i] * (s[i] - 'a' + 1));
Обрабатываем q запросов.
while(q--)
{
scanf("%c",&c);
if(c == '?')
{
scanf("%d
%d %d\n",&l,&r,&len);
Пересчитаем позиции запросов так
чтобы l < r.
if(l >
r) swap(l, r);
Выводим ответ на запрос о равенстве
подстрок.
printf((Sum(l + len - 1) - Sum(l - 1)) *
Pow[r - l] ==
Sum(r + len - 1) - Sum(r - 1) ? "+" : "-");
}
else
{
scanf("%d
%c\n",&l,&c);
На данный момент m[l] = sl * pl. Следует произвести присваивание
s[l] = c или m[l] = c * pl. На дереве Фенвика промоделируем прибавление m[l] = m[l] + c
* pl – sl
* pl.
Inc(l, (c - s[l]) * Pow[l]);
s[l] = c;
}
}
printf("\n");