如果 S S S是 T T T的子序列，那么会返回 ∣ T ∣ − ∣ S ∣ |T|-|S| ∣T∣−∣S∣，否则会大于这个值。
那么可以先查询单个字符，选取最小的答案，这个字符一定在 T T T中出现过。这样我们得到了串长。
那么，我们继续询问连续一段相同字符可以得到每个字符的出现次数。
然后用类似归并的过程合并两个字符集不交的子序列，步数为 c n t a + c n t b − 1 cnt_a+cnt_b-1 cnta+cntb−1
那么每次找长度最短的两个子序列合并即可。因为 Huffman \text{Huffman} Huffman树的树高不超过 log L \log L logL，所以总步数 L log L L\log L LlogL。
显然要分析答案的结构。。。
一个递增数可以拆成若干串 1 1 1。。。
然后有一个很仙的转化。。。
因为 111 ⋯ 11 ⏟ i = 1 0 i − 1 9 \underbrace{111\cdots 11}_{i}=\frac{10^i-1}{9} i 111⋯11=910i−1
所以 N = ∑ i = 1 n + 1 k i ( 1 0 i − 1 ) 9 N=\sum_{i=1}^{n+1}\frac{k_i(10^i-1)}{9} N=∑i=1n+19ki(10i−1)
设 k k k表示总的 111 ⋯ 11 111\cdots 11 111⋯11的个数，那么 9 N + k = ∑ i = 1 n + 1 k i 1 0 i 9N+k=\sum_{i=1}^{n+1}k_i10^i 9N+k=∑i=1n+1ki10i。左边显然是 10 10 10的倍数，那么如果 k k k合法的话 9 N + k 9N+k 9N+k的数位之和应该不超过 k k k，同时我只能把 1 0 i 10^i 10i拆成 10 10 10个 1 0 i − 1 10^{i-1} 10i−1，那么要求 k k k和 ∑ i = 1 n + 1 k i \sum_{i=1}^{n+1}k_i ∑i=1n+1ki模 9 9 9同余。等式两边模 9 9 9发现这恒成立。
同时我们观察到 k k k不会超过 10 n 10n 10n，那么我们模拟高精度加法就能做到均摊 O ( 1 ) O(1) O(1)，总复杂度 O ( n ) O(n) O(n)。
好难的模拟题。。。
从左端飞出去其实只有一种情况，那就是第一个就是 A A A，否则肯定会从右端飞出去。
如果遇到 B B B就直接走过去，如果遇到 A A A就把垫背的反转，然后走过去。
好妙的结论啊。。。
探究一次操作后 i i i的状态。
把 A A A看成 0 0 0， B B B看成 1 1 1。
如果最高位是 0 0 0，那么把最高位反转成 1 1 1。
否则 s s s取反并左移一位。（左移会溢出最高位）