Задача №114955. Сколько строк меньше
Дан набор \(D\) из \(n\) строк и строка \(s\). Требуется быстро находить число строк, лексикографически меньших \(s\), в наборе \(D\).
С заданной строкой \(s\) выполняются \(q\) модификаций, каждая из которых задается парой из числа \(k_i\) и символа \(c_i\). Модификация \((k_i, c_i)\) заключается в том, что все символы строки \(s\), начиная с \(k_i\) и до конца строки, заменяются на символ \(c_i\).
Например, пусть исходно строка \(s\) была равна « anatoly », тогда последовательность запросов \((5, \mathtt{o})\), \((3, \mathtt{b})\), \((7, \mathtt{x})\) будет менять строку следующим образом:
Строка \(a\) лексикографически меньше строки \(b\), если \(a \ne b\) и выполнено одно из двух условий:
- \(a\) является префиксом строки \(b\);
- для некоторого \(i\) первые \(i\) символов строки \(a\) равны соответствующим символам строки \(b\), а \(a_{i+1}<b_{i+1}\).
Первая строка входных данных содержит два целых числа \(n\) и \(q\) — количество строк в наборе \(D\) и количество модификаций (\(1 \le n, q \le 10^6\)).
Во второй строке находится строка \(s\), состоящая из не более чем \(10^6\) строчных латинских букв.
В следующих \(n\) строках содержатся строки набора \(D\). Каждая строка состоит из строчных латинских букв. Суммарная длина строк в \(D\) не превосходит \(10^6\).
Следующие \(q\) строк содержат описания модификаций. Описание состоит из числа \(k_i\) и строчной буквы латинского алфавита \(c_i\), разделенных пробелом (\(1 \le k_i \le |s|\)).
В первой строке выведите число строк в наборе \(D\), которые лексикографически меньше изначальной строки \(s\).
Затем выведите \(q\) строк. В \(i\)-й строке выведите ответ после \(i\)-й модификации.
В первом тесте из примера строка изменяется следующим образом:
- Изначальная строка « anatoly » лексикографически меньше всех строк набора, поэтому ответ на задачу \(0\).
- После первого изменения строка становится « anatooo » и такая строка есть в наборе, однако ответ на задачу по прежнему будет \(0\), так как она не меньше, текущей.
- Затем строка становится « anbbbbb », что лексикографически больше, чем « anatooo » и « anba », но меньше чем « anbbbbu » и « boris », таким образом ответ \(2\).
- После последнего изменения строка станет « anbbbbx », что лексикографически больше « anatooo », « anba » и « anbbbbu », ответ \(3\).
4 3 anatoly boris anatooo anbbbbu anba 5 o 3 b 7 x
0 0 2 3
5 5 abcde buz ababa build a aba 1 b 3 z 2 u 4 z 1 a
3 3 3 4 4 1