Задача
Саша находится в процессе творческого поиска. Она хочет сплести ещё одну фенечку, но испытывает сложности при выборе цветов. Сейчас все $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 |
+- |
Код программы
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 |
#include <iostream> #include <vector> #include <algorithm> using namespace std; vector<unsigned long long> t; vector<unsigned long long> codes; const unsigned long long prime = 61; vector<unsigned long long> pows; void build (int v, int tl, int tr) { if (tl == tr){ t[v] = codes[tl] * pows[tl - 1]; } else { int tm = (tl + tr) / 2; build (2 * v, tl, tm); build (2 * v + 1, tm + 1, tr); t[v] = t[2 * v] + t[2 * v + 1]; } } unsigned long long sum (int v, int tl, int tr, int l, int r) { if (l > r){ return 0; } if (l == tl && r == tr) return t[v]; int tm = (tl + tr) / 2; return sum (2 * v, tl, tm, l, min(r, tm)) + sum (2 * v + 1, tm + 1, tr, max(l, tm + 1), r); } void update (int v, int tl, int tr, int pos, unsigned long long newVal) { if (tl == tr) t[v] = newVal * pows[pos - 1]; else { int tm = (tl + tr) / 2; if (pos <= tm) update (v*2, tl, tm, pos, newVal); else update (2 * v + 1, tm + 1, tr, pos, newVal); t[v] = t[2 * v] + t[2 * v + 1]; } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n, k; cin >> n >> k; t.resize(4 * n); string a; cin >> a; codes.resize(n + 1); for(int i = 1; i <= n; i++){ codes[i] = a[i - 1] - 'A' + 1; } pows.resize(n + 1); pows[0] = 1; for(int i = 1; i <= n; i++){ pows[i] = pows[i - 1] * prime; } build(1, 1, n); cin.ignore(); for(int t = 0; t < k; t++){ char q; cin >> q; if(q == '?'){ int i, j, len; cin >> i >> j >>len; if(i > j){ swap(i, j); } if(sum(1, 1, n, i, i + len - 1) * pows[j - i] == sum(1, 1, n, j, j + len - 1)){ cout << "+"; } else{ cout << "-"; } } else if(q == '*'){ int temp; char c; cin >> temp >> c; update(1, 1, n, temp, c - 'A' + 1); } cin.ignore(); } return 0; } |
Решение задачи
Наивный алгоритм тратит на выполнение первого запроса $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