原帖传送门

依照数据范围，可以有 3 个优化等级。
注：这里我们将回文数的处理视为 $\mathrm{O}(\log n)$

1. 枚举前半段，检查全回文数是否在 $[a,b]$ 里面，$\mathrm{O}(\sqrt n \log n)$

2. 注意到如果 $a=1$ 的话可以二分查找最大的符合条件的前半段。奇数位和偶数位的最大符合前半段不同，所以找完奇数前半段数 $a_i$ 之后在在 $[1, a_1]$ 找 $a_2$ 即可。
   当 $a\ne 1$ 时，只需要算出 $[1,b]$ 内的回文数数量，然后减去 $[1,a-1]$ 内的回文数即可。$\mathrm{O}(\log^2 n)$.

3. 又注意到最大的符合条件的同奇偶前半段一定是 $b$ 的前半段或其减 1，不同奇偶一定形如 $99\cdots9$.
   e.g. 1234: 分别为 1221 和 999.
   于是用 $\mathrm{O}(\log n)$ 判断最大的符合条件的前半段。和 2 一样，也是用 $[1,b]$ 的答案减 $[1,a-1]$ 的答案。