2026 牛客暑期多校 2 - I - Imperfect Dot Sums and Cross Sums
给定了 \(n \le 10^5\) 个随机的三维向量 \(V_i = (x_i, y_i, z_i)\)，值域在 \(\pm 10^6\) 范围。
有 \(q \le 10^5\) 次询问，每次询问给出一个区间 \([L,R]\)，以及一个随机的三维向量 \(T\)。
你需要回答 \(\sum_{i=l}^r (\vert{}V_i \cdot T\vert{} + \Vert{}V_i \times T\Vert{})\) 的值，只要误差在 \(10\%\) 以内即可接受。
PS. 这个式子是指点积的绝对值 + 叉积的模长。
观察每个单项 \(v_i = (\vert{}V_i \cdot T\vert{} + \Vert{}V_i \times T\Vert{})\)，那么:
- 点积的绝对值：\(\vert{}V_i \cdot T\vert{} = \Vert{}V_i\Vert{} \Vert{}T\Vert{} \vert{}\cos \theta_i\vert{}\)
- 叉积的模长：\(\Vert{}V_i \times T\Vert{} = \Vert{}V_i\Vert{} \Vert{}T\Vert{} \sin \theta_i\)
提取公因式就是 \(v_i = \Vert{}V_i\Vert{} \Vert{}T\Vert{} (\vert{}\cos \theta_i\vert{} + \sin \theta_i)\)，同时注意后半部分 \(f(\theta_i) \in [1, \sqrt 2]\)
Sol1 蒙特卡洛
首先有一个很 naive 的做法，随机区间中的 \(B\) 个向量计算贡献，取平均值，再乘区间长度。
不过由于区间里模长的分布是不平均的，这样做的方差太大，是无法满足精度的要求的。
考虑这个事实，如果一个向量的模长 \(\Vert{}V\Vert{}\) 越大，它对答案的贡献就越大。
我们可以通过加权，调整每个向量被随机到的概率 \(p_i = {\Vert{}V\Vert{} \over W}\)，这里 \(W\) 是区间所有模长之和。
此时单次采样的估计量是
也就是说估计量 \(Y\) 被限制在了 \(W\Vert{}T\Vert{}\) 到 \(1.414 W\Vert{}T\Vert{}\) 之间，单次相对标准差不超过 \(20\%\)。
我们重复 \(B = 100\) 次采样，相对误差就到了 \(\frac{20\%}{\sqrt B} = 2\%\)，完全够用，加权平均后即可通过 Link。
Sol2-1 离线 \(\epsilon\)-聚类
官方 std 的做法（感觉比较一般吧，但是也很有启发）
我们先离线所有询问，取一个询问向量 \(T\)，将与其夹角小于 \(\epsilon\) 的全部打包为一组。
假设这组询问向量都是一样的，在\(O(n)\) 预处理前缀和以后，可以 \(O(1)\) 回答每个询问。
正确性比较显然，因为这一组的 \(f(\theta_i)\) 都比较接近，误差不会太大。
STD 说期望会进行 \(O(\log^2 \epsilon)\) 轮，故复杂度为 \(O(n+q) \log^2 \epsilon\)。
我怎么感觉是会进行 \(O(\epsilon ^ {-2})\) 轮，总复杂度为 \(O(n \epsilon ^ {-2})\) 呢，代码应该很难写...
关于为什么认为是 $O(\epsilon ^ {-2})$
打包相当于射出了一个半角为 \(O(\epsilon)\) 的圆锥，投影到单位球面的表面积为 \(2 \pi (1 - \cos \epsilon)\)。
由于 eps 应该是不太大的，泰勒展开 $\cos \epsilon \approx 1 - \frac{\epsilon^2}{2} $
代入表面积公式得到每次覆盖的球表面积大致是 \(\pi \epsilon^2\)，期望轮次为 \(\frac{4\pi}{\epsilon^2} = O(1/\epsilon^2)\)
Sol2-2 球面分块
既然可以把询问打包，无视它们的角度差异，我们当然可以反过来把序列上的向量打包。
可以按极角和方位角进行划分出 \(20 \times 30 = 600\) 个网格，并算出每个网格正中心的标准向量。
接下来我们为了回答区间询问，不妨再对序列进行分块，具体的做法是做一个二维前缀和：
- 维护 \(dp[b][m]\) 表示在前 \(m\) 个块中，第 \(b\) 个网格里的向量模长之和。
- 假设块内所有模长都是集中在标准向量上的。
查询对散块暴力，再枚举每个网格 \(O(1)\) 查询整块的贡献，这样是 \(O((n + q) \sqrt n)\) 了。
别人的代码 link，太美丽了这个做法。
Sol3 多项式拟合
不知道大家有没有参加过算子比赛，一个常用手法是用低次多项式逼近复杂函数，在精度误差范围内加速。
我们令 \(y = \cos^2 \theta_i\)，那么
可以用切比雪夫逼近找到 \(P(y) = 1.0675 + 1.25 y - 1.25y^2\) 替换 \(\sqrt{y} + \sqrt{1 - y}\)。
可以验证 \(P(y)\) 的精度，在 \([0, 1]\) 内最大误差为 \(6.75\%\)，满足题目要求。
在多项式替换后，我们将 \(y = \cos^2 \theta_i = \frac{(V_i \cdot T)^2}{\Vert{}V_i\Vert{}^2 \Vert{}T\Vert{}^2}\) 代回原方程：
把 \(T\) 提出来以后，提前对所有 \(V_i\) 相关的 \(0,2,4\) 次项分别维护 \(1,6,15\) 共 \(22\) 个前缀和。
即可在 \(O(1)\) 时间里回答每个询问，预处理写起来比较吃技巧 link，跑得飞快 500ms。