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）：

T(n)=\max\{\displaystyle\max_{k\le u}\{T(n-k)+k\sqrt V+\frac{k(k-1)}{2}\},\displaystyle\max_{k\ge u}\{T(k-1)+T(n-k)+n\}\}

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

A(n)=\displaystyle\max_{k\le u}\{A(n-k)+\frac{k(k-1)}{2}+k\sqrt V\} B(n)=\displaystyle\max_{k\ge u}\{B(n-k)+B(k-1)+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)。

考虑代入法：

T(n)=\max\{\displaystyle\max_{k\le u}\{A(n-k)+k\sqrt V+\frac{k(k-1)}{2}\},\displaystyle\max_{k\ge u}\{B(k-1)+B(n-k)+n\}\}=\max\{A(n),B(n)\}=O(n\sqrt V)

终于结束啦。