题解：P9218 「TAOI-1」Apollo

如果你看懂了题目，你会发现 $f(a)$ 其实就代表 $a$ 的小数位数。

而 $g(x,y)$ 怎么求呢？

显然，如果 $x$ 或 $y$ 之间有整数，也就是它们的整数部分不同。如果整数部分相同，那么如果第一位小数不同，则答案为 $1$。如果整数和第一位小数都相同，但是第二位小数不同，则答案为 $2$，以此类推。

但是上面的讨论是有问题的：实际上，如果 $x$ 或 $y$ 的某一位小数相同（前面也相同），但是某个数字后面没有小数位了，则由于区间是闭区间所以包括 $x$ 和 $y$，答案就是 $f(x)$ 或 $f(y)$，但是根据上述讨论需要继续往后看直到 $y$ 的某一位不为 $0$。做法也很简单，因为要满足这样的条件必须 $x$ 或 $y$ 转化为字符串后一个是另一个的前缀。

等等，前缀？我们在讨论数学为什么要看这个。实际上，如果把 $x,y$ 都转化为字符串并令两个字符串的最后一个字符不和任何字符相同，则 $g$ 函数值就是：

如何把这个讨厌的整数部分的检测去掉呢？非常简单，因为贡献是 $0$ 所以可以不算，事先对所有数字分组，整数部分相同的分到同一组，组内统计即可。组间答案是 $0$ 的。

那么，假设整数部分相同，如何统计答案呢？

这就是一个串串题了。Trie 树板子题，建出 Trie 树后求一个节点和其它所有节点的 LCA 深度之和。在每个节点上标记子树中有多少个字符串即可。