Примечание
Для удобства будем называть «подозрительными» те подотрезки, для которых соответствующие им строки являются префиксами \(S\), то есть те, подозрительность которых может быть не нулевой.
В результате расшифровки в первом примере из условия после всех запросов строка \(S\) равна «abacaba», а все \(w_i = 1\), то есть подозрительность всех подозрительных подотрезков просто равна \(1\). Посмотрим, как получается ответ после каждого запроса:
1. \(S\) = «a», у массива \(W\) есть единственный подотрезок — \([1, \ 1]\), и соответствующая ему подстрока равна «a», то есть всей строке \(S\), то есть она является префиксом \(S\), и подозрительность подотрезка равна \(1\).
2. \(S\) = «ab», подозрительные подотрезки: \([1, \ 1]\) и \([1, \ 2]\), всего \(2\).
3. \(S\) = «aba», подозрительные подотрезки: \([1, \ 1]\), \([1, \ 2]\), \([1, \ 3]\) и \([3, \ 3]\), всего \(4\).
4. \(S\) = «abac», подозрительные подотрезки: \([1, \ 1]\), \([1, \ 2]\), \([1, \ 3]\), \([1, \ 4]\) и \([3, \ 3]\), всего \(5\).
5. \(S\) = «abaca», подозрительные подотрезки: \([1, \ 1]\), \([1, \ 2]\), \([1, \ 3]\), \([1, \ 4]\), \([1, \ 5]\), \([3, \ 3]\) и \([5, \ 5]\), всего \(7\).
6. \(S\) = «abacab», подозрительные подотрезки: \([1, \ 1]\), \([1, \ 2]\), \([1, \ 3]\), \([1, \ 4]\), \([1, \ 5]\), \([1, \ 6]\), \([3, \ 3]\), \([5, \ 5]\) и \([5, \ 6]\) всего \(9\).
7. \(S\) = «abacaba», подозрительные подотрезки: \([1, \ 1]\), \([1, \ 2]\), \([1, \ 3]\), \([1, \ 4]\), \([1, \ 5]\), \([1, \ 6]\), \([1, \ 7]\), \([3, \ 3]\), \([5, \ 5]\), \([5, \ 6]\), \([5, \ 7]\) и \([7, \ 7]\) всего \(12\).
Во втором примере из условия после всех запросов \(S\) = «aaba», \(W = [2, 0, 2, 0]\).
1. \(S\) = «a», подозрительные подотрезки: \([1, \ 1]\) (подозрительность \(2\)), в сумме \(2\).
2. \(S\) = «aa», подозрительные подотрезки: \([1, \ 1]\) (\(2\)), \([1, \ 2]\) (\(0\)), \([2, \ 2]\) (\(0\)), в сумме \(2\).
3. \(S\) = «aab», подозрительные подотрезки: \([1, \ 1]\) (\(2\)), \([1, \ 2]\) (\(0\)), \([1, \ 3]\) (\(0\)), \([2, \ 2]\) (\(0\)), в сумме \(2\).
4. \(S\) = «aaba», подозрительные подотрезки: \([1, \ 1]\) (\(2\)), \([1, \ 2]\) (\(0\)), \([1, \ 3]\) (\(0\)), \([1, \ 4]\) (\(0\)), \([2, \ 2]\) (\(0\)), \([4, \ 4]\) (\(0\)), в сумме \(2\).
В третьем примере из условия после всех запросов \(S\) = «abcde», \(W = [7, 2, 10, 1, 7]\).
1. \(S\) = «a», подозрительные подотрезки: \([1, \ 1]\) (\(7\)), в сумме \(7\).
2. \(S\) = «ab», подозрительные подотрезки: \([1, \ 1]\) (\(7\)), \([1, \ 2]\) (\(2\)), в сумме \(9\).
3. \(S\) = «abc», подозрительные подотрезки: \([1, \ 1]\) (\(7\)), \([1, \ 2]\) (\(2\)), \([1, \ 3]\) (\(2\)), в сумме \(11\).
4. \(S\) = «abcd», подозрительные подотрезки: \([1, \ 1]\) (\(7\)), \([1, \ 2]\) (\(2\)), \([1, \ 3]\) (\(2\)), \([1, \ 4]\) (\(1\)), в сумме \(12\).
5. \(S\) = «abcde», подозрительные подотрезки: \([1, \ 1]\) (\(7\)), \([1, \ 2]\) (\(2\)), \([1, \ 3]\) (\(2\)), \([1, \ 4]\) (\(1\)), \([1, \ 5]\) (\(1\)), в сумме \(13\).