NOIP 集训考试记录

edisnimorF / 2023-07-25 / 原文

7.24 数据结构

4089: 大嘴乌鸦

4090: 艾莎

设选择区间为 $S=[l,r]$，试把它分裂成两半 $S_1=[l,x],S_2=[x+1,r]$．

有 $S$ 的平均数 $$ave_S=\frac{ave_{S_1}(x-l+1)+ave_{S_2}(r-x+1)}{r-l+1}$$

显然 $ave_{S_1}$ 和 $ave_{S_2}$ 至少有一个 $\ge ave_S$．

事实上肯定是一个大于等于 $ave_S$，一个小于等于 $ave_S$．

如果能选择一个合适的分割点，使得 $S_1,S_2$ 的长度都大于 $1$．那么对于任意的 $S$，都可以找到比它更小的区间的组合来表达它，并使得答案不会更劣．

考虑边界情况，只有长度为 $2,3$ 的区间不能再分．

然后我们得出结论：存在一种答案区间的长度 $\le 3$．

4091: 沙奈朵 .

奇怪的分块．

其实还是自由度的问题（大概）．

假设每次询问的颜色 $x$ 固定．考虑已知两个子区间 $L,R$ 的答案，如何合并．
首先有 $ans=ans_L+ans_R$．然后考虑过区间中点的答案．

一个有贡献的过区间中点的子区间形如 $L$ 中由 $x$ 颜色出发的一个后缀和 $R$ 中一个前缀的拼接．容易想到预处理两块然后直接乘法原理统计答案．

记 $Val(F)$ 表示子序列 $F$ 的贡献：$\sum_{i\in F} [a_i\neq a_{i+1}]$．

对于区间 $S$，记

\[\begin{aligned} A_S&=\sum_{i\in S,col_i=x}Val(suf_i)\\ B_S&=\sum_{i\in S,col_i=x}Val(pre_{i-1})\\ C_S&=\sum_{i\in S}[col_i=x]\\ \end{aligned} \]

跨区间答案即为

\[A_L\times C_R+B_R\times C_L \]

那么，如何更新 $A,B$？

有

\[\begin{aligned} A=A_L+C_L\times Val(R)+A_R\\ B=B_L+C_R\times Val(L)+B_R \end{aligned} \]

如果单独拿出一种颜色，这个信息还是容易维护的．容易使人迷惑，也是使得线段树在此题上不好维护的关键在于询问颜色不定．

这里是我的一些思考

考场上第一次看到这道题的时候，之所以没有去想如何维护一种颜色的答案信息，有一定的原因在于被误导意图直接维护所有颜色的答案．

所以对于这种询问自由度较高的题目应尝试思考固定一些限制的解题方法．可能对写题有帮助．

那么分块然后套用上面的方式维护所有颜色的答案即可．

4092: 绒绒鸹

恶心树剖题．

对于每条重链维护当前处于这条重链的元素．

当某一个元素摆脱当前重链的时候暴力更新．考虑一条链经过的不同重链条数至为 $\log$ 条．这个操作的总次数不超过 $n \log n$．

然后问题就转化成了一个链上问题．

假设在 $T$ 时刻查询节点 $u$ 的答案．考虑 $u,v$ 属于重链 $C$．$v$ 上的一个元素跳上 $C$ 的时刻为 $T'$．那么其 $T$ 时刻在 $u$ 上的判定为：

\[T-T'=Dep_u-Dep_v \]

显然移项：

\[Dep_v-T'=Dep_u-T \]

可以每个重链开一个桶．

然后最后元素可能会跳到环上．

对于环上的判定需要改动一下：

\[T-T'+k\times Sz=Ord_u-Ord_v \]

其中 $Ord$ 是给环上的节点按转圈的顺序标上一个序号．在变一变：

\[\begin{aligned} T-T' \equiv Ord_u-Ord_v\\ Ord_v-T' \equiv Ord_u-T \end{aligned} \]

好好好．

7.25 数据结构优化 DP?

4101: OIL

把式子中的枚举断点提到前面来．
然后式子就变成了

\[\sum_{i<n}\sum_{x\le i,y>i} mxpre_i\times mnsuf_j \]

预处理

\[\begin{aligned} F_i&=\sum_{j \le i} mxpre_i\\ G_i&=\sum_{j \ge i} mxsuf_i \end{aligned} \]

易得

\[ans=\sum_{i<n} F_i\times G_{i+1} \]

接下来就是重头戏：