2022ICPC杭州-K,A,C,G,M个人题解如何获取？

K - Master of Both trie #逆序对 #字符串 问题描述 灰机教授是字符串宗师与高级数据结构师，这天他想到了这样一个问题：按顺序给定 \(n\) 个仅包含小写字母的字符串，按照字典序，这些串当中有几个逆序对？ 按照字典序来处理，这个问题并不困难；然而，在 \(q\) 个不同的平行世界中，字典序并不像我们现在所处的世界这样规定。 准确来说，每个平行宇宙的字母表都是一个长度为 \(26\) 的包含了每一种小写字母的串，表示字母之间的顺序关系。 我们称 \(a\) 的字典序小于 \(b\) 当且仅当满足以下条件之一： \(a\) 是 \(b\) 的前缀，但 \(a \neq b\)； 在 \(a\) 与 \(b\) 对应字符不同的第一个位置上，字符串 \(a\) 在这个位置上的字符在字母表中出现的位置早于字符串 \(b\) 的。 一个长度为 \(n\) 的序列 \(a\) 的逆序对数是满足 \(1 \leq i < j \leq n\)，\(a_j < a_i\) 的 \((i,j)\) 的数目。