P11661 无聊

考虑最值分治，当然也可以用笛卡尔树，这两个东西本质一样。

以下内容视 $n,V$ 同阶。

先考虑 $50$ 分的做法：

假设当前分治的区间为 $x\sim y$，令 $x\sim y$ 最大的 $a_i$ 为 $a_k$。枚举小的一边（这里只讨论枚举左边，右边的同理），这时固定了 $b_l,a_k$，变为求 $m$ 次：$k\sim r$ 中 $b_l\equiv b_i\pmod{a_k}$ 的 $i$ 的个数。存成 $m$ 个询问，形如 $l,r,x,y$，求 $l\sim r$ 中模 $x$ 为 $y$ 的 $b_i$ 的个数。

根号分治跑询问即可，时间复杂度 $O(n\sqrt n\log n)$。

对于 $100$ 分的做法：

思考为什么最值分治枚举小的一边时间复杂度是 $O(n\log n)$。因为其对左区间长度与右区间长度取了最小值，这题也可以考虑这么优化。

假设当前分治区间短的一边的长度为 $q$，对短边跑根号分治的时间复杂度为 $O(q\sqrt V)$。若 $q\sqrt V>n$，显然不如暴力枚举另一边，那么就有：$T(n)=\displaystyle\max_{2k\le n}\{T(k-1)+T(n-k)+\min\{k\sqrt V,n\}\}$，可得 $T(n)=O(n\sqrt V)$。

时隔多日后补个证明，别打我。

令 $u=\frac{n}{\sqrt V}$（这是函数内的 $n$）。

把 $T(n)$ 拆成（以下所有内容，默认 $2k\le n$）：

考虑从其中弄出两个函数：

对于 $A(n)$ 绝对是 $k$ 越大越好，于是 $k=u$，易证 $A(n)=O(n\sqrt V)$。

易证 $A(n)=B(n)$。

考虑从 $1\to n$ 计算 $T(n)$，对于 $n\le\sqrt V$ 有：$T(n)=A(n)=B(n)$。

考虑代入法：

终于结束啦。