请注意，本题解所述解法因常数问题无法通过，请使用常数更加优秀的实现解决。

此题解仅供参考。

唔，连分数！

显然信息不具有交换律，但仍然满足结合律。

简单来说，维护当前区间的连分数函数，使得其形如：

（使用连项式或者数学归纳即可得证）

则其复合满足结合律。且易证上下总互质。

同时，维护当前区间的字符串等价信息：

• 上个元素末尾是 $1$ 时的转移矩阵、区间 $f(z)$。
• 上个元素末尾不是 $1$ 时的转移矩阵、区间 $f(z)$。
• ……

感觉还要分类讨论……

听说有结论，但我不会。

然而众所周知，一个 E 发挥第二种作用当且仅当上一位是 W。

于是区间可以分为以下几种更细致的信息：

• 整段全是 E。
• 整段全是 W。
• 全场开头若干（至少 $1$ 个） E，然后均（至少 $1$ 个） W。
• 除去以上几类外，开头是 E/W，末尾是 E/W，中间还复合一个 $f$ 函数。

对第四类情况，如果开头是 W ，只用维护开头两项分别加多少、中间部分的 $f$ 长啥样、末尾两项初始化为多少；如果是 E，要对上一位的两种情况分别维护一次信息。

对第一、二、三类情况，比较显然。

然后直接上暴力分类讨论 $49$ 种合并就完了。

记得封装起来，以免下面调试困难。

感觉比较难写。

但是要支持 reverse、flip 操作，这就非常吐。

直接平衡树维护即可。

被卡常了。

写了一发正解过了。

但是上面的方法能做。仅供参考。