CF700D Huffman Coding on Segment

Alice 想要向 Bob 发送一条重要的信息。信息 $a=(a_{1},...,a_{n})$ 是一个正整数（字符）序列。 为了压缩消息，Alice 想要使用二叉 Huffman 编码。我们回顾一下，二叉 Huffman 编码或二叉前缀码是一个函数 $f$，它将消息中出现的每个字符映射为某个二进制字符串（即只包含字符 '0' 和 '1' 的字符串），对于任意两个不同的字符 $a_{i}$ 和 $a_{j}$，都有 $f(a_{i})$ 不是 $f(a_{j})$ 的前缀（反之亦然）。消息 $a_{1},a_{2},...,a_{n}$ 的编码结果是每个字符编码的拼接，即字符串 $f(a_{1})f(a_{2})...f(a_{n})$。Huffman 编码非常有用，因为如果已知函数 $f$，压缩后的消息可以简单且唯一地解码。通常选择编码方式以最小化压缩消息的总长度，即字符串 $f(a_{1})f(a_{2})...f(a_{n})$ 的长度。 由于安全原因，Alice 不想发送完整消息。她会选择消息的若干子串，分别发送。对于每个给定的子串 $a_{l_i}...a_{r_i}$，她想知道使用 Huffman 编码后最小可能的编码长度。请你帮她解决这个问题。

输入的第一行包含一个整数 $n$（$1 \leq n \leq 100000$）——原始消息的长度。第二行包含 $n$ 个整数 $a_{1},a_{2},...,a_{n}$（$1\leq a_{i} \leq 100000$）——消息的各个字符。 第三行包含一个整数 $q$（$1 \leq q \leq 100000$）——询问的数量。 接下来 $q$ 行，每行描述一个询问。第 $i$ 行包含两个整数 $l_{i}$ 和 $r_{i}$（$1 \leq l_{i} \leq r_{i} \leq n$），分别表示该子串的左端和右端位置。位置从 $1$ 开始编号。子串可以任意重叠，相同的子串在输入中可能出现多次。

输出 $q$ 行，每行一个整数，表示子串 $a_{l_i}...a_{r_i}$ 使用 Huffman 编码时最小可能的编码长度。

对于第一个询问，对应子串的一种最优编码方式是将 $1$ 映射为“0”，$2$ 映射为“10”，$3$ 映射为“11”。 注意，可以将某个字符映射为空字符串（如样例中的第 5 个询问）。 由 ChatGPT 5 翻译