CF1286E Fedya the Potter Strikes Back

Fedya has a string $ S $ , initially empty, and an array $ W $ , also initially empty. There are $ n $ queries to process, one at a time. Query $ i $ consists of a lowercase English letter $ c_i $ and a nonnegative integer $ w_i $ . First, $ c_i $ must be appended to $ S $ , and $ w_i $ must be appended to $ W $ . The answer to the query is the sum of suspiciousnesses for all subsegments of $ W $ $ [L, \ R] $ , $ (1 \leq L \leq R \leq i) $ . We define the suspiciousness of a subsegment as follows: if the substring of $ S $ corresponding to this subsegment (that is, a string of consecutive characters from $ L $ -th to $ R $ -th, inclusive) matches the prefix of $ S $ of the same length (that is, a substring corresponding to the subsegment $ [1, \ R - L + 1] $ ), then its suspiciousness is equal to the minimum in the array $ W $ on the $ [L, \ R] $ subsegment. Otherwise, in case the substring does not match the corresponding prefix, the suspiciousness is $ 0 $ . Help Fedya answer all the queries before the orderlies come for him!

N/A

N/A

For convenience, we will call "suspicious" those subsegments for which the corresponding lines are prefixes of $ S $ , that is, those whose suspiciousness may not be zero. As a result of decryption in the first example, after all requests, the string $ S $ is equal to "abacaba", and all $ w_i = 1 $ , that is, the suspiciousness of all suspicious sub-segments is simply equal to $ 1 $ . Let's see how the answer is obtained after each request: 1\. $ S $ = "a", the array $ W $ has a single subsegment — $ [1, \ 1] $ , and the corresponding substring is "a", that is, the entire string $ S $ , thus it is a prefix of $ S $ , and the suspiciousness of the subsegment is $ 1 $ . 2\. $ S $ = "ab", suspicious subsegments: $ [1, \ 1] $ and $ [1, \ 2] $ , total $ 2 $ . 3\. $ S $ = "aba", suspicious subsegments: $ [1, \ 1] $ , $ [1, \ 2] $ , $ [1, \ 3] $ and $ [3, \ 3] $ , total $ 4 $ . 4\. $ S $ = "abac", suspicious subsegments: $ [1, \ 1] $ , $ [1, \ 2] $ , $ [1, \ 3] $ , $ [1, \ 4] $ and $ [3, \ 3] $ , total $ 5 $ . 5\. $ S $ = "abaca", suspicious subsegments: $ [1, \ 1] $ , $ [1, \ 2] $ , $ [1, \ 3] $ , $ [1, \ 4] $ , $ [1, \ 5] $ , $ [3, \ 3] $ and $ [5, \ 5] $ , total $ 7 $ . 6\. $ S $ = "abacab", suspicious subsegments: $ [1, \ 1] $ , $ [1, \ 2] $ , $ [1, \ 3] $ , $ [1, \ 4] $ , $ [1, \ 5] $ , $ [1, \ 6] $ , $ [3, \ 3] $ , $ [5, \ 5] $ and $ [5, \ 6] $ , total $ 9 $ . 7\. $ S $ = "abacaba", suspicious subsegments: $ [1, \ 1] $ , $ [1, \ 2] $ , $ [1, \ 3] $ , $ [1, \ 4] $ , $ [1, \ 5] $ , $ [1, \ 6] $ , $ [1, \ 7] $ , $ [3, \ 3] $ , $ [5, \ 5] $ , $ [5, \ 6] $ , $ [5, \ 7] $ and $ [7, \ 7] $ , total $ 12 $ . In the second example, after all requests $ S $ = "aaba", $ W = [2, 0, 2, 0] $ . 1\. $ S $ = "a", suspicious subsegments: $ [1, \ 1] $ (suspiciousness $ 2 $ ), totaling $ 2 $ . 2\. $ S $ = "aa", suspicious subsegments: $ [1, \ 1] $ ( $ 2 $ ), $ [1, \ 2] $ ( $ 0 $ ), $ [2, \ 2] $ ( $ 0 $ ), totaling $ 2 $ . 3\. $ S $ = "aab", suspicious subsegments: $ [1, \ 1] $ ( $ 2 $ ), $ [1, \ 2] $ ( $ 0 $ ), $ [1, \ 3] $ ( $ 0 $ ), $ [2, \ 2] $ ( $ 0 $ ), totaling $ 2 $ . 4\. $ S $ = "aaba", suspicious subsegments: $ [1, \ 1] $ ( $ 2 $ ), $ [1, \ 2] $ ( $ 0 $ ), $ [1, \ 3] $ ( $ 0 $ ), $ [1, \ 4] $ ( $ 0 $ ), $ [2, \ 2] $ ( $ 0 $ ), $ [4, \ 4] $ ( $ 0 $ ), totaling $ 2 $ . In the third example, from the condition after all requests $ S $ = "abcde", $ W = [7, 2, 10, 1, 7] $ . 1\. $ S $ = "a", suspicious subsegments: $ [1, \ 1] $ ( $ 7 $ ), totaling $ 7 $ . 2\. $ S $ = "ab", suspicious subsegments: $ [1, \ 1] $ ( $ 7 $ ), $ [1, \ 2] $ ( $ 2 $ ), totaling $ 9 $ . 3\. $ S $ = "abc", suspicious subsegments: $ [1, \ 1] $ ( $ 7 $ ), $ [1, \ 2] $ ( $ 2 $ ), $ [1, \ 3] $ ( $ 2 $ ), totaling $ 11 $ . 4\. $ S $ = "abcd", suspicious subsegments: $ [1, \ 1] $ ( $ 7 $ ), $ [1, \ 2] $ ( $ 2 $ ), $ [1, \ 3] $ ( $ 2 $ ), $ [1, \ 4] $ ( $ 1 $ ), totaling $ 12 $ . 5\. $ S $ = "abcde", suspicious subsegments: $ [1, \ 1] $ ( $ 7 $ ), $ [1, \ 2] $ ( $ 2 $ ), $ [1, \ 3] $ ( $ 2 $ ), $ [1, \ 4] $ ( $ 1 $ ), $ [1, \ 5] $ ( $ 1 $ ), totaling $ 13 $ .