251202 模拟测 总结

挂分惨烈（？

我 T1 的 \(5\) 分呢。

Pro.A

对，所以为什么你 \(Ans\) 的初值不设为 \(n+1\)，为什么。我问你呢你明明知道有负数啊！！！1111（崩溃

通过十分严谨的证明大力瞎猜结论，我们发现，将 \(a\) 升序排序后，最终选择的一定是 \(a\) 的一段后缀。不会证，但是感性地理解一下，为了最大化 \(\sum b\) 显然会是升序的，并且由于有负数可能只是一段后缀。

那么做法就很显然咯，把 \(a\) 的每个后缀的答案像算后缀和一样都算出来，取最大方案即可。

这里算答案的时候，需要算一下这个 \(a_i\) 会提供多少个 \(k\)，正常就是 \(n-i\) 但是在于你后面可能有重复，因此要开个桶啥的记一下。

然后就没然后了。

Pro.B

行行行我承认我推式子差，问题在于你都没给这玩意儿变形啊？第一步都没做叫啥叫？？？

首先看这个原来的式子。

\[\sum_{l=1}^{n} \sum_{r=l}^{n} ( \sum_{i=l}^{r} a_i ) \times ( \sum_{i=l}^{r} b_i ) \]

这个式子换一种写法。

\[\sum_{l=1}^{n} \sum_{r=l}^{n} ( \sum_{i=l}^{r} a_i ) \times ( \sum_{i=l}^{r} b_i ) \]

显然可以待定系数一下，设答案为：

\[\sum_{i=1}^{n} b_i q_i \]

再设：

\[q_i = \sum_{j=1}^{n} p_{i,j} a_j \]

由于所有修改都仅和 \(b\) 有关，所以 \(p,q\) 都不会修改。

然后我们再回归分析原题。

如果对区间 \([l,r]\) 的 \(b\) 值集体增加 \(k\)，那么它对原答案就会增加

\[\sum_{i=l}^{r} k \times q_i = k\sum_{i=l}^{r}q_i \]

那么只要求出 \(q\) 就好了。

\(q\) 又是与 \(p\) 有关的，现在来考虑 \(p\) 的定义。

观察式子可以发现，它指的是既包含了 \(i\)，并且包含了 \(j\) 的区间的个数。

那么当 \(i \le j\) 时，\(p_{i,j} = i \times (n-j+1)\)，否则 \(p_{i,j} = j \times (n-i+1)\)。

但是这样求依然是 \(O(n^2)\) 的玩不了。

设 \(p_i = x_i + y_i\)，不难发现有 \(x_i = x_{i-1} - \sum_{j=1}^{i-1} a_j \times j\)，\(y_i = y_{i-1} + \sum_{j=i}^{n} a_j \times (n-j+1)\)，所以预处理 \(a_i \times i\) 和 \(a_i \times (n-i+1)\) 的前缀和就可以做咯。

Pro.C

发现这个期望是假的，其实是求平均数。
发现这个树形 DP 是假的，其实是做树形 DP。

发现这个期望是假的其实是平均数，于是就有了柿子

\[\dfrac{\sum_{i,j} dis(i,j) \times 2(m-1)!}{m!} \]

记连接 \(x,y\) 条边在 \(\sum_{i,j} dis(a_i,a_j)\) 这个式子中被计过的边数为 \(num_{i,j}\)，那么一次操作对这个式子的影响就是增加了 \(k \sum_{E(x,u)} num_{x,u}\)，显然只需要知道 \(num\) 值就能 \(O(1)\) 解决。

考虑使用树形 DP 处理出 \(num\)，我们考虑这样一条边，它可以把树分为两个部分，那么就是这两个部分的特殊点的个数乘积就是 \(num\) 的值了，树形 DP 预处理子树中特殊点的个数即可。

于是就做完咯，有个地方要记得做乘法逆元搞除法。

Pro.D

根号分治还是太强了喵 /bx

我们发现，如果 \(x\) 比较小的话，可以对于每个 \(x\) 记录其循环节，然后每次修改只维护循环节与循环节的前缀和。询问时遍历每个 \(x\)，计算询问区间内有多少完整的循环节与散的循环节的区间和即可。

这样做的时间复杂度差不多为 \(O((n+m)x)\) 的，如果 \(x\) 在 \(\sqrt{n}\) 左右的范畴下，是完全没有什么问题的。

嘿哦，看到根号你居然没有想到根号分治，吓坏猫了！

那么当 \(x > \sqrt{n}\) 时我们怎么办呢，由于只有不到 \(\sqrt{n}\) 个段，可以每个段都暴力线段树维护，带个 \(\log\)，有点小慢。

于是我们只好尝试做到能 \(O(1)\) 区修 \(O(\sqrt{n})\) 区查的分块。由于要 \(O(1)\) 区修那肯定是差分维护。

那么查询区间 \([l,r]\) 的和就是 \(\sum_{i=l}^{r} \sum_{j=1}^{i} c_j\)，其中 \(c\) 是差分数组。

推一下柿子，我们得到一个东西：

\[\sum_{i=l}^{r} \sum_{j=1}^{i} c_j = (r-l+1) \sum_{i=1}^{l-1} c_i + \sum_{i=l}^{r} c_i \times (r-i+1) \]

左边这个东西是好维护的，但是右边这个东西好像很难处理啊，这个该怎么办呢？

我们对该序列进行根号分块，注意这里是分块，类似莫队的思想。对于每一个块，分别额外维护出 \(\sum_{i=L}^{R} c_i \times (R-i+1)\)，那么对于一个整块的答案就是 \((r-R)\sum_{i=L}^{R} c_i + \sum_{i=L}^{R} c_i \times (R-i+1)\)。

这两个东西都是可以在修改的时候 \(O(1)\) 维护的，那么中间的连续块就可以这样算出了，而零散的块由于长度不超过 \(\sqrt{n}\) 直接枚举都能处理，于是你就把那什么线段树的 \(\log\) 给干没了。

那么你就可以 \(O(n \sqrt{n})\) 地解决这个问题了。