结论1：如果曲奇 \(c\) 当 \(k=x\) 时会被剩下，那么当 \(k=x+1\) 时亦会被剩下。
感性理解即可。显然初始集合越大，曲奇越不容易被换走。
结论2：原问题等价于以下问题：每次给出一个曲奇 \(c\)，遇到 \(S_i=\)'S' 且 \(c>B_i\) ，或 \(S_i=\)'B' 且 \(c<B_i\) 就交换 \(c,B_i\)（交换会保留到下次操作），最终的 \(c\) 就是本次答案的增量。
假设说这次将 \(A\) 换到了 \(B\) 的位置上，下一次 \(B\) 也一定可以被 \(A\) 换走，只是可能有更优的决策 \(C\)。既然 \(C\) 比 \(A\) 要优，先用 \(A\) 换掉 \(B\)，再用 \(C\) 换掉 \(A\) 和直接用 \(C\) 换掉 \(B\) 本质相同，对原问题答案自然没有影响。
转化后我们不难发现 \(S_i\) 具有可并性。对于一段连续的 \(S_i=\)'S'，即相当于尝试用 \(x\) 换掉这一段的 \(\min\)，反之亦然（不妨分别称之为 \(\min\) 段和 \(\max\) 段）。
结论3：若相邻的 \(\min,\max\) 段 \(X,Y\) 满足 \(\min\{X\} \geq \max\{Y\}\) ，两个段交换不影响答案。
按 \(x\) 大小讨论一下即可，注意到当段数大于等于 \(2\) 时，每次交换段数至少减一。
结论4：若相邻的 \(\min,\max\) 段 \(X,Y(\min\{X\}<\max\{Y\})\) 大小分别为 \(|X|,|Y|\)，最多经过 \(|X|+|Y|\) 次后即有 \(\min\{X\} \geq \max\{Y\}\)。
同样按 \(x\) 大小讨论一下即可。
实际上，直接实现上述算法便可通过本题。具体复杂度分析如下：
假设一共有 \(L\) 对匹配段，根据抽屉原理必然至少存在 \(\frac{L}{2}\) 对匹配段满足 \(|X_i|+|Y_i| \leq \frac{2M}{L}\)，也就是说每执行 \(\frac{2M}{L}\) 次操作段数就会减半，共会减半 \(\log M\) 次，同时由于每次复杂度不超过 \(\frac{2M}{L} \times L =2M\)，总复杂度即 \(O(M \log M)\)。
于是本题复杂度取决于合并堆的方式，使用可并堆可以做到 \(O(M \log M)\)，或直接对 priority_queue 启发式合并，复杂度为 \(O(M \log^2 M)\)。