HBC230856[HAOI2008]排名系统,平衡树,字符串hash,伸展树Splay,数据结构,字符串Encoded Strings I题解

全网最全C++题库，助您快速提升编程技能！题库丰富多样，涵盖各个领域，让您在练习中不断成长！

Tommy has just invented an interesting string encoding algorithm, which is described below. For every string SSS, we may define a character-mapping function FSF_SFS, which maps every character occurring in SSS to a lowercase letter, as below FS=chrF_S = operatorname{chr}FS=chr where chroperatorname{chr}chr is the (i+1)(i+1)(i+1)-th lowercase Latin letter, and G(c,S)GG(c,S) is the number of different characters after the last occurrence of ccc in SSS. To encode a string SSS by Tommy's algorithm, replace every character ccc in SSS by FSF_SFS simultaneously. For example, the encoded string of "abc" is "cba", and the encoded string of "cac" is "aba". You are given a string of length nnn and then encode all the nnn nonempty prefixes. Your task is to find the encoded string that has the greatest lexicographical order among all the encoded strings.

Tommy has just invented an interesting string encoding algorithm, which is described below. For every string SSS, we may define a character-mapping function FSF_SFS​, which maps every character occurring in SSS to a lowercase letter, as below FS(c)=chr⁡(G(c,S))F_S(c) = operatorname{chr}(G(c, S))FS​(c)=chr(G(c,S)) where chr⁡(i)operatorname{chr}(i)chr(i) is the (i+1)(i+1)(i+1)-th lowercase Latin letter, and G(c,S)G(c, S)G(c,S) is the number of different characters after the last occurrence of ccc in SSS. To encode a string SSS by Tommy's algorithm, replace every character ccc in SSS by FS(c)F_S(c)FS​(c) simultaneously. For example, the encoded string of "abc" is "cba", and the encoded string of "cac" is "aba". You are given a string of length nnn and then encode all the nnn nonempty prefixes. Your task is to find the encoded string that has the greatest lexicographical order among all the encoded strings.

标签： HBC230856[HAOI2008]排名系统 平衡树 字符串hash 伸展树Splay 数据结构 字符串Encoded Strings I题解