题意
https://codeforces.com/contest/2006/problem/D
分析
考虑如果没有修改怎么重排最优。先把最大值丢进序列，再把最小值丢进序列，再把次大值丢进序列，再把次小值压进去，以此类推。感性理解的话不难发现这是最优情况，具体证明可以考虑调整法（但我懒）。
令 \(b\) 为 \(a\) 排序后的结果，那么 \(\max a_i\cdot a_{i+1}=\max b_i\cdot b_{n-i+1}\)，简而言之就是 \(k\) 大值乘 \(k\) 小值的乘积最大值。如果 \(n\) 为奇数那么最中间的那个数没用。
如果要修改的话，显然要把当前最大值修改为 \(1\)，然后就变成了 \(k+2\) 大值和 \(k\) 小值的乘积最大值。
那么一个三方暴力就呼之欲出了：若一个 \(p\) 大值和一个 \(q\) 小值（满足 \(p\ge q\)）的乘积大于 \(k\)，那么修改次数就需要至少为 \(\dfrac{p-q}{2}+1\)，最终答案就是对所有的 \(\dfrac{p-q}{2}+1\) 取 max。注意这里不需要讨论 \(p-q\) 是奇数的情况，因为此时乘积大于 \(k\) 那么 \(p\leftarrow p+1\) 后乘积更大且修改次数不变。
当然这个暴力很容易优化成平方 log，但对正解没啥启发作用。
发现 \(k\) 很小，结合乘法运算的性质，考虑根号分治，把 \(\le \sqrt k\) 的数分为一类（称之为第一类），\(>\sqrt k\) 的数分为一类（称之为第二类）。显然两个第二类的数相乘必定大于 \(k\)，两个第一类的数相乘必定小于 \(k\)。考虑把第二类的数重标号，将 \(x\) 重标号为 \(\sqrt k+\lfloor\dfrac{k}{x}\rfloor\)，表示这个数在和第一类数中大于 \(\dfrac{k}{x}\) 的数相乘会大于 \(k\)，加上 \(\sqrt k\) 只是为了区分第一类数。不难发现此时不同的数种类只有 \(2\sqrt k\) 个。
考虑询问。由于不同的数种类只有 \(2\sqrt k\) 个，所以我们完全可以把区间内每种数的出现次数存下来，跑一遍前缀和就可以知道值域在某段区间内的数的个数。
分类讨论：
- 两个二类数相乘（前提是需要有至少两个二类数）：把排名最小的二类数和排名最大的二类数相乘，能让修改次数卡满。
- 一类数和二类数相乘：枚举每个二类数 \(x\)，求出排名最大的 \(x\) 以及所有 \(>x-\sqrt k\) 的数中排名最小的 \(y\)，能让修改次数卡满。
但是，如果维护出 \(s_{c,i}\) 表示前缀 \(i\) 中 \(c\) 的出现次数的话是 \(O(n\sqrt k)\) 的，空间开不下。一种容易想到的方法是考虑莫队维护每种数的出现次数，时间复杂度 \(O(n\sqrt n+q\sqrt k)\)，空间复杂度 \(O(n+q+\sqrt k)\)，可以通过。
代码：https://codeforces.com/contest/2006/submission/278952523
标签：Iris,dfrac,大值,sqrt,次数,相乘,Products,CF2006D,二类 From： https://www.cnblogs.com/dcytrl/p/18404878