多校A层冲刺NOIP2024模拟赛17
T1 网格
签到题
注意到 \(+\) 与 \(\times\) 由于优先级其实是分开的，所以可以考虑每到达一个 \(+\) 计算一次贡献（乘上一个组合数），然后将前置贡献重新赋值为方案数，DP 只需考虑连续 \(\times\) 段即可。
时间复杂度 \(O(nm)\)。
T2 矩形
根号分治
发现不管怎么枚举总会出现一些特殊情况使得复杂度存在瓶颈，并且虽然值域是 \([1,n]\) 但总共只有 \(O(n)\) 个点，图是很稀疏的。
这启发我们把特殊的拿出来分讨去做，考虑以列为单位，并设置阈值 \(B\)，一列中点数大于 B 的记为大段，小于的记为小段，则只需要考虑 \(3\) 种情况的贡献。
-
大段与小段之间的贡献
注意到大段的个数不会超过 \(O(\frac{n}{B})\) 个，考虑枚举每一个大段，然后去计算所有小段对它的贡献。具体的当枚举到一个大段时，在值域上标记它所拥有的点，然后枚举小段，查询每个有多少个相同纵坐标，记为 tot，则一个小段的贡献为 \(\binom{tot}{2}\)。
这一部分的时间复杂度为 \(O(\frac{n^2}{B})\)。 -
大段与大段之间的贡献
有两种做法
第一种同上即可解决。
第二种可以使用 \(bitset\) 优化，具体的枚举任意两个，然后用 \(bitset\) 按位与计算相同个数，然后同上组合数计算贡献，时间复杂度为 \(O(B^2\frac{n}{w})\) -
小段与小段之间的贡献
注意到小段只有至多 \(O(B)\) 个元素，可以考虑每个点枚举 \(O(B)\) 次去做。
具体的，可以在值域上枚举下端点，然后对于所有包含这个点的段进行计算，即将所有在下端点上方的点加入到值域 \(cnt\) 数组中，由于钦定了下端点，所以 \(cnt\) 中直接就是答案。
考虑时间复杂度，发现每个点至多会被枚举 \(O(B)\)，而总共有 \(O(n)\) 个点，这一部分的时间复杂度为 \(O(nB)\) 的。
当 \(B\) 取 \(\sqrt n\) 时总复杂度最优，为 \(O(n\sqrt n)\)，由于本题特殊数据很难造，并且就算强度高也远远达不到这个上界所以跑的飞快。
双倍经验 [Ynoi Easy Round 2024] TEST_132
T3 集合
不会
T4 倒水
概率期望，数据结构优化DP，线段树
注意到一个性质。
只要有一次向前倒就结束了，证明显然。
那么有一个推论。
记 \(b_i\) 为 \(i\) 当前的量，\(i\) 倒出去的水的量为 \(\min(a_j,b_i)\)，证明考虑分讨，当 \(j\) 中没有水时显然，而有水时 \(i\) 中的水一定是从 \(j\) 中来的，所以一定达不到 \(j\) 的上界。
那么可以设计状态进行 DP，设 \(f_{i,j}\) 表示当到 \(i\) 要倒水时 \(i\) 有 \(j\) 单位体积的水的概率。
根据上述结论，发现向前转移能直接计算贡献即可，而向后转移则转移到 \(f_{k,\min(a_k,j)}\)（此时仍需计算自己的贡献）。
现在就得到一个 \(O(n^3)\) 的做法。
显然能前缀和优化，将刷表改为填表，等转移完后再计算贡献即可优化至 \(O(n^2)\),这一部分比较重要，下面具体讲讲。
设辅助数组 \(s1_{i,j}=\sum_{a\le i,b\le j}f_{a,b},s2_{i,j}=\sum_{a\le i,b\le j}bf_{a,b},hs_i=\sum_{1\le j\le n}\max(0,i-a_j)\)，即 \(s1,s2\) 分别是概率、期望的前缀和。
- 转移
-
计算贡献
设 \(res_i\) 表示 \(i\) 的期望（答案），下面为了方便就直接写等号了，实际上为两部分之和。-
向前倒以及向后倒剩下的
\(res_i=\sum_{j=1}^{a_i} hs_jf_{i,j}\frac{1}{n-1}\)
-
别的向前倒，倒给它的
把 \(\min\) 去掉，所以得分讨。
-
从大于 \(a_i\) 倒来
\(res_i=(s1_{n,n}-s1_{i,n}-s1_{n,a_i}+s1_{i,a_i})a_i\frac{1}{n-1}\)
-
从小于 \(a_i\) 倒来
\(res_i=(s2_{n,a_i}-s2_{i,a_i})\frac{1}{n-1}\)
-
-
\(O(n^2)\) 比较平凡。
考虑优化
只需考虑 \(O(n^2)\) 的瓶颈部分。
即求解 \(hs,s1,s2\) 数组，以及（用 \(hs\) 数组）计算倒剩下的贡献。
对于求解 \(hs\) 数组可以对 \(a\) 数组排序后求解，就将这一部分复杂度降低到 \(O(nlogn)\)。
如果只维护高度值域的前缀和（即 \(s_{i,j}=\sum_{k\le j}f_{i,k}\) ）会发现一些很好的性质！
\[\begin{aligned} &\begin{cases} f_{i,j}=\frac{1}{n-1}s_{i-1,j}\quad &j< a_i \\ f_{i,j}=\frac{1}{n-1}\sum_{k\ge j}s_{i-1,k}\quad &j=a_i \end{cases} \\ &\begin{cases} s_{i,j}=(1+\frac{1}{n-1})s_{i-1,j}\quad &j< a_i \\ s_{i,j}=s_{i-1,j}+\frac{1}{n-1}f_{i,j}\quad &j=a_i \end{cases} \end{aligned} \]如果用线段树去维护值域的话（ 扫描线 ）则 \(j< a_i\) 在只需要区间乘即可，而 \(j=a_i\) 则需区间求和，单调修改。
考虑怎么计算贡献
-
\(hs\)
将 \(hs_i\) 作为系数放在线段树上，扫描到 \(i\) 时区间求和即可。
-
\(s1\)
发现只有 \(4\) 个值 （ 矩形面积 ） ，按第一维处理，扫描到 \(i\) 时处理一次（ 扫描线的套路 ），扫描结束处理一次。
-
\(s2\)
只需结合一下 \(hs,s1\) 的做法即可，即在线段树上每一个位置，将位置作为系数，然后扫描线求矩形面积。
这样就只需要维护一个支持区间乘法，单点修改，区间求和的线段树即可。
时间复杂度 \(O(nlogn)\)，常数很小，能轻松爆标。
