推歌推過了今天就不再推了。

傳送

考慮暴力，最樸素的暴力就是每次查詢都把所有插入操作掃一遍統計前綴。

全都掃一遍太暴力了！既然是字符串題，那么一些基本的數據結構肯定是需要的。比如我們就可以建立一顆字典樹，并在這顆字典樹上操作。

每次插入字符串 \(S\) 時我們考慮 \(S\) 影響的前綴，發現只有 \(S\) 的前綴會被 \(S\) 影響，那么我們直接在 \(S\) 前綴的每個節點上打個標記記錄其有一個該前綴的字符串。如果刪去的話把標記去掉一個就好了。

我們發現我們要查詢第一次超過某個值的時間。于是我們可以給每個節點維護一個 vector，每次達到了新的最大值就把當前的時間插入進去，查詢的時候直接輸出即可。

看起來還是很暴力！但是算一下復雜度，發現是 \(O(n|S|)\) 的，完全可以通過！

然后這個題就做完了。個人認為完全沒有紫。