本人在浏览题解区时发现 这篇题解 是不使用 splay 树但是采用了将区间左右端点旋转到位后打标记的做法的唯一一篇。

具体地，他是先建出类似线段树的结构，然后每次修改时，将 $l - 1$ 旋转到根，将 $r + 1$ 旋转到根下面，并给 $r + 1$ 的左儿子打上标记。

正确性没有问题。但是复杂度对不对呢？这样的数据可以将其卡掉：

区间长度 $10^5$，翻转操作次数 $10^5$，前 $5 \times 10^4$ 次第 $i$ 次翻转区间 $[2i - 1, 2i]$，后 $5 \times 10^4$ 次第 $i + 5 \times 10^4$ 次翻转区间 $[2i - 1, 2i]$。

实测这篇题解的代码在我的机子上跑这组数据的时间稳定在 20 秒以上，这是比较符合没有完全卡满的 $O(n^2)$ 复杂度的表现的。

实际上，通过输出树的形态可以发现，在执行完前 $5 \times 10^4$ 次操作后，树的形态已经成了高度为 $O(n)$ 的左偏链挂单点了。