本题用随机性质的做法

rt，题解都说是 $O(qn^2)$ 的但是没一个证明。我的理解：每次一个位置 $0\to1$ 要 $O(qL^2)$ 重算这个区间 $dp$ 值，总复杂度 $O(q\sum_{i}sz_i^2)=O(qn^2\log^2n)$（其中 $sz_i$ 为笛卡尔树中 $i$ 的子树 size）。