CF777D Cloud of Hashtags

Vasya 是“Mouse and keyboard”组织公共主页的管理员，他的日常工作是发布与竞技编程相关的新闻。对于每条新闻，他还会创建一个标签列表，以方便按主题查询。对于本题，标签被定义为以一个符号“\#”开头、其余部分由小写英文字母组成的字符串。标签的长度被定义为去掉“\#”后剩余字符的数量。 主页的主管理员告诉 Vasya，标签必须按字典序排列（字典序的定义见提示部分）。 Vasya 很懒，他并不想真的去改变早已发布的标签顺序。相反，他决定对某些标签删除后缀（即字符串末尾连续的一段字符）。他可以删除任意数量的字符，甚至可以将整个字符串都删掉，只保留一个“\#”。Vasya 想要选择一种删除方式，使得被删除的总字符数最小。如果有多种最优方案，他接受任意一种。

输入的第一行包含一个整数 $n$（$1\leq n\leq 500000$），表示当前需要编辑的标签数。 接下来的 $n$ 行每行包含恰好一个标签，且每个标签长度均为正。 保证所有标签（也就是所有字符串去掉“\#”后的总长度）之和不超过 $500000$。

输出按照某种最优方案处理后的标签，每个标签占一行。

长度为 $m$ 的单词 $a_1,a_2,\dots,a_m$ 被认为在字典序上不大于长度为 $k$ 的单词 $b_1,b_2,\dots,b_k$ ，当且仅当，有以下两种情况之一成立： - 存在最小的下标 $i$ 满足 $a_i\ne b_i$，且 $a_i$ 按字母表顺序早于 $b_i$，即第一个不同的字符处 $a$ 的字母早于 $b$； - 如果没有这样的下标 $i$ 且 $m\leq k$，即第一个单词是第二个单词的前缀或两个单词完全相同。 如果序列中的每一个单词（除最后一个外）在字典序上都不大于下一个单词，则称这个序列按字典序有序。 对于由小写英文字母组成的单词来说，字典序和词典中的单词顺序相同。 根据上述定义，只包含一个“\#”的标签，在字典序上不超过任何其它合法标签。因此，在第三个样例中，不能只对后三个标签做缩短，而保持前两个标签不变。 由 ChatGPT 5 翻译