D. Assumption is All You Need
又是一道思维题，还是没想出来，看了官解感觉巨麻烦，又翻了下民间题解，变得简洁易懂多了。蒟蒻太笨了qwq...
给定两个排列 \(a, b\)，可以交换排列 \(a\) 的任意一个逆序对，问能否将 \(a\) 变成 \(b\)，并求一个合法的操作过程。
由于只能交换逆序对，显然在操作过程中，逆序对的数量只会减少。可以察觉到：逆序对越多，可操作性越强，越有利于我们得到期望序列。因此我们可以贪心地想：让较大的数尽可能地在左边，这样序列的可操作性就会放大。
考虑从左到右依次匹配：假设当前正在匹配第 \(i\) 个位置，分情况讨论：
- \(a[i] = b[i]:\) 已经匹配，直接跳过
- \(a[i] < b[i]:\) 由于只能交换更小的数到该位置，因此可以判定无解。
- \(a[i] > b[i]:\) 此时在 \(i\) 位置的右侧必有满足 \(a[i] > a[j] = b[i]\) 的位置 \(j\)，可以将其交换过来以匹配位置 \(i\)，但这样太草率了，因为在位置 \(j\) 特别靠后的情况下，直接交换会导致 \(a[i]\) 到位置 \(j\) 上，这样不一定是最优的，因为在将 \(a[j]\) 交换到位置 \(i\) 前，\(a[i]\) 可能会有位置更靠左的去处（前面说了，让较大的数尽可能地在左边）。我们可以通过多次交换来实现它：在将 \(a[j]\) 交换到位置 \(i\) 之前，可以先将 \(a[i]\) 交换到 \(a[j]\) 左侧的某个位置，使得交换后 \(a[j]\) 仍能被换到位置 \(i\)。具体地，我们可以从 \(i\) 位置开始，向右找第一个 \(a[i] > a[k]\) 且 \(a[k] \geq b[i]\) 的位置 \(k\) 作一次交换,持续这样的操作，直到位置 \(i\) 匹配。与直接一次交换匹配相比，这样做可以在使得位置 \(i\) 匹配的情况下，让原 \(a[i]\) 尽可能靠左；同时我们发现，所有交换的位置在全部交换操作完成后，相对位置不变，这样做也使得逆序对的损失达到最小化，显然更有利于后面的操作。
复杂度 \(O(n^{2})\)。
后来才发现官解也是这种做法，晦涩难懂的部分全部都是对这种做法的证明。确实，严格证明还是 \(too\space hard\) 的。
补完后还是觉得太难想了，看来距离牌子还差得很远。。。
code
B. A Plus B Problem
一道简单模拟，开始用了 \(O(q\log^{2}n)\) 的线段树 + 二分，TLE7; 后来看了官解，才发现二分是可以优化掉的，直接用平衡树或者 \(set\) 维护满足 \(r1[i] + r2[i] \neq 9\) 的所有位置 \(i\) 即可，复杂度是 \(O(q\log n)\) 的，但还是 TLE 7。可能是实现得比较繁琐，常数太大了？看民间题解里也有用线段树区间赋值做的，应该还是自己的实现有点问题。。。
脑子糊了，明天再看。
code_tle7