Задача
Саша находится в процессе творческого поиска. Она хочет сплести ещё одну фенечку, но испытывает сложности при выборе цветов. Сейчас все $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 |
import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { private static long[] t; private static long[]codes; private static final long prime = 61; private static long[] pows; private static 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]); } } private static 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, Math.min(r, tm)) + sum (2 * v + 1, tm + 1, tr, Math.max(l, tm + 1), r); } private static void update (int v, int tl, int tr, int pos, 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]); } } public static void main(String[] args) throws Exception{ BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in)); String[] params = bufferedReader.readLine().split(" "); int n = Integer.parseInt(params[0]); codes = new long[n + 1]; pows = new long[n + 1]; t = new long[4 * n]; int k = Integer.parseInt(params[1]); String a = bufferedReader.readLine(); for (int i = 1; i <= n; i++) { codes[i] = a.charAt(i - 1) - 'A' + 1; } pows[0] = 1; for (int i = 1; i <= n; i++) { pows[i] = pows[i - 1] * prime; } build(1, 1, n); for (int t = 0; t <k; t++) { char q = (char) bufferedReader.read(); bufferedReader.skip(1); if (q == '?') { String[] query = bufferedReader.readLine().split(" "); int i = Integer.parseInt(query[0]); int j = Integer.parseInt(query[1]); int len = Integer.parseInt(query[2]); if (i > j) { int temp = i; i = j; j = temp; } if(sum(1, 1, n, i, i + len - 1) * pows[j - i] == sum(1, 1, n, j, j + len - 1)){ System.out.print("+"); } else{ System.out.print("-"); } } else if(q == '*') { String[] query = bufferedReader.readLine().split(" "); int temp = Integer.parseInt(query[0]); char c = query[1].charAt(0); update(1, 1, n, temp, c - 'A' + 1); } } } } |
Решение задачи
Наивный алгоритм тратит на выполнение первого запроса $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