P7739 [NOI2021] 密码箱

· · 题解

这里是考场上想出来的凡人做法，但好像和其他人的做法有些出入？这里是直接维护的 a 数组的贡献。

首先观察如何用一串 W 和 E 来得到 a 数列，发现如果是在中间的连续一段的 EEE...EWWW...W 的话，E 的个数和 W 的个数刚好确定连续的两个 a 的值。

再考虑边界，如果第一个字符是 W，那么最前面会多出来个 a_0=0，如果第一个字符是 E 则无影响。

如果最后一个字符是 W，那么最后面的 a_k+1\to a_k，因为没有 E 把它减 1，如果最后一个字符是 E，那么最后面会多出来个 a_k=1。

这些在回答询问时都可以处理。

考虑 a 数列对答案的贡献：我们考虑 a_i+\dfrac{1}{a_{i+1}+\dfrac{1}{...+\frac{1}{x}}}，我们希望预处理后对于一个有理数 x 快速求出这个式子的值。

设 x=\frac{q}{p}，当前层为的 a 的值为 a_k，那么每从 x 往上走一层，有 p+q\cdot a_k\to q'，q\to p'。

那么设贡献为 \dfrac{c\cdot p+d\cdot q}{a\cdot p+b\cdot q} ，转移 a,b,c,d 即可，此部分通过暴力验证是正确的。

接下来的事情就简单了，考虑操作对 a 数列带来变化。

  1. APPEND：改变最后一个 a，可能在最后加入 a，并可能改变尾字符。

  2. FLIP：可能把某两个 a 拆开，并可能改变首尾的字符。

  3. REVERSE：可能把某两个 a 拆开，并可能改变首尾的字符，同时中间贡献的转移翻转。

改变某个或某两个 a 的操作是平凡的，只要你能找到拆开后左右的大小，改变首尾字符也是平凡的，不再赘述。

考虑中间的转移被翻转怎么办，显然我们可以把正着转移的贡献和倒着转移的贡献都算出来，翻转直接 swap 两个的贡献即可。

如果使用块链来维护上述过程是十分契合的，每次拆开两个 a 或改变一个 a 时可以直接拆块然后暴力重构整个块，复杂度是 O(\sqrt{n}) 的。

翻转贡献的办法也已经说过，而 a 数组本身被翻转用块链也很好实现，这样的话找任意一个位置都是 O(\sqrt{n}) 的。

为什么没写出来？你觉得我考场上能写块链？

下来后发现平衡树也能轻易维护上述操作，裂开。