Самая страшная история

Автор задачи: Тимур Гараев, разработчик: Даниил Орешников

Будем хранить всю строку в виде декартова дерева по неявному ключу, элементами которого являются символы строки. Помимо этого, будем в каждой вершине хранить информацию о ее поддереве:

Сведем все описанные в задаче запросы к запросам на таком декартовом дереве:

  1. Чтобы по позиции символа в строке $$$i$$$ вернуть номер слова и его номер в этом слове, достаточно заметить, что при выполнении $$$\mathtt{split}(i)$$$, в левом поддереве $$$l$$$ содержатся все предшествующие слова и следующие за ними пробелы, таким образом номер слова будет равен $$$\mathtt{cnt}(l) + 1$$$, а номер позиции в слове будет равен $$$i - \mathtt{last}(l)$$$.

  2. Наоборот, чтобы по номеру слова $$$w$$$ и позиции в нем $$$p$$$ найти позицию в строке, найдем $$$(w - 1)$$$-й пробел, после чего отступим от него $$$p$$$ позиций вправо. Чтобы найти позицию определенного пробела в строке, можно спускаться из корня в левое или правое поддерево в зависимости от того, чему равно $$$\mathtt{cnt}(l)$$$.

  3. Для удаления или вставки символа достаточно несколько раз воспользоваться стандартными split и merge по позиции.

Таким образом, осталось только реализовать все это, после каждого действия пересчитывая все три параметра в изменившихся вершинах. Время работы равно $$$\mathcal{O}(q \log n)$$$.