YuJiaheAKIOI 那篇队列题解的代码，有一个令我疑惑的地方

while (used[f.st] && f.st <= f.ed) f.st ++; // 如果已经被取了

这意味着某些被取过的元素将会再次遍历到，所以最坏时间复杂度不一定是 $\Theta(n)$ 的。

蒟蒻想出了一种数据：

41
1 1 1 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 1 0 0 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 1 1 1

即形如

t个1 + (t-2)个0 + (t-4)个1 + (t-6)个0 +...+4个1 + 2个0 + 1个1 
+ 2个0 + 4个1+...+ (t-6)个0  + (t-4)个1 + (t-2)个0 + t个1

容易得到 $t = \left \lfloor \sqrt{\frac{2n-1}{2} } \right \rfloor$

对于这种数据，那行代码的运行次数：

当 0 0 1 0 0 左右两个 0 合并时，运行 $2$ 次；

当 1 1 1 1 0 0 1 0 0 1 1 1 1 左右两个 1 合并时，运行 $8$ 次；

当 0 0 0 0 0 0 1 1 1 1 0 0 1 0 0 1 1 1 1 0 0 0 0 0 0 左右两个 0 合并时，运行 $18$ 次；

当 1 1 1 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 1 0 0 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 1 1 1 左右两个 1 合并时，运行 $32$ 次；

可以看出，次数为 $2\times(1^2+2^2+3^2+...+t^2) = t(t+1)(2t+1)/3$，而 $t$ 为 $\sqrt n$ 级的。

所以其最坏时间复杂度应该是 $O(n \sqrt n)$。