blog。NOIP2023 T1。
可以对字符串随意交换，即可以重排每个单词。对于询问 \(i\)，最优方案显然是将 \(\forall j\ne i\) 的 \(w_j\) 重排至字典序最大，将 \(w_i\) 重排至字典序最小。
这件事情本质是将 \(w_i\) 与 \(\min\limits_{j\ne i} w_j\) 比较。在开始时将全部串重排至字典序最大，取出最小与次小的编号（即为 \(p\) 与 \(q\)）。
询问时，单独重排 \(w_i\) 至字典序最小；若 \(i\ne p\)，只需比较 \(w_i\) 与 \(w_p\)；否则比较 \(w_i\) 与 \(w_q\) 即可。
code，时间复杂度 \(O(nm\log m)\) 或 \(O(nmV)\)。