• luogu P17825 [COCI 2026/2027 #1] 三堆箱子 / Tri

    考虑分治。要把 \([1,n]\) 排好序，我们首先把他按照值域对半分成两堆数，把数小的那一堆排好序，再把另一堆排好序，最后就完成了。

    具体的，设 \(solve(l,r,fr,to)\) 表示把 \([l,r]\) 的数从 \(fr\) 柱子上移到 \(to\) 柱子上并排好序，每次对半分，不断递归分治下去就行。

    分析一下复杂度，总共 \(logn\) 层，每层只有值域划分的 \(n\) 次操作，最后每个叶子最多操作一次，总次数是 \(nlogn+n\) 的，可以通过本题。

  • luogu P17826 [COCI 2026/2027 #1] 水 / Voda

    这里没有思维，只有纯粹的ds！！！

    考虑只需要维护一下前缀/后缀最长贪心上升子序列的相关信息即可。具体过程和“楼房重建”这个题是一样的，使用所谓“兔队线段树”，就是在 \(pushup\) 时在树上二分到最底层即可。反正一大堆要维护的东西。

  • luogu P17807 [ICPC 2019 Nanchang R] Bitwise Tree

    好题，位并行。

    首先看到 \(d\) 非常小，于是直接暴力对所有 \(d\) 把整个图的权值全设一遍即可，无非复杂度多个 \(d\) ……

    于是我们去掉了 \(d\) 的部分，考虑剩下的部分怎么做。

    首先考虑拆位，这样 \(a_i\in [0,1]\) ，状态就非常少了，把每条路径看作一个布尔函数，直接维护每个子树传入 \(0/1\) 时对应的三种和就行了。

    这样复杂度多个 \(log\) 过不去，注意到直接把所有位放一起考虑就行了，也就是所谓的“位并行”。

    复杂度 \(O(nd+q)\) 。

  • CF2134F Permutation Oddness

    \(dp\) 好题。

    首先值域非常小，我们把每个二元组对应的贡献先列出来找找规律。发现两个数一样时贡献为 \(0\) ，只有 \((0,2)\) 和 \((1,3)\) 对应的贡献是 \(2\) ，剩下全是 \(1\) 。

    由于 \(2\) 的贡献情况很苛刻，于是这启发我们把 \(0\) 和 \(2\) 放一起考虑，\(1\) 和 \(3\) 放一起考虑。

    我们把所有 \(0,2\) 染成蓝色，所有 \(1,3\) 染成红色。那么贡献为 \(1\) 的缝隙就是红蓝之间的缝隙，贡献为 \(0\) 的就是一个值连续段内部的缝隙，贡献为 \(2\) 的就是颜色连续段中除了 \(0\) 的剩下的缝隙。

    显然两种颜色是独立的，我们考虑分别处理好两种颜色内部的贡献，再拼起来。

    拿 \(0,2\) 举例。只考虑这两种值，设 \(g_l\) 表示分成 \(l\) 个值连续段的方案数，显然由插板法 \(g_l=\sum_{l_1+l_2=l}\begin{pmatrix}{c_0-1} \\ {l_1-1} \end{pmatrix}\begin{pmatrix}{c_2-1} \\ {l_2-1} \end{pmatrix}\begin{pmatrix}2 \\ [l_1=l_2]\end{pmatrix}\)，设 \(f_{i,j}\) 表示分成 \(i\) 个颜色连续段，总贡献为 \(j\) 的方案数，则枚举在 \(k_1\) 个不同值之间切一刀，在 \(k_2\) 个相同值之间切一刀，即 \(f_{k_1+k_2+1,2(l-1-k1)+k1+k2}=\sum_{k_1}^{l-1}\sum_{k_2}^{c_0+c_2-l}g_l*\begin{pmatrix}l-1 \\ k_1\end{pmatrix}\begin{pmatrix}c_0+c_2-l \\ k_2\end{pmatrix}\) 。

    这样一切都处理好了，最后把两种颜色的 \(f\) 数组合并即可。

    计算一下复杂度。预处理 \(g\) 是 \(O(n)\) 的（\(l_1\) 的枚举范围是 \(O(n)\) ，\(l_2\) 的枚举范围是 \([l_1-1,l_1+1]\) ）预处理 \(f\) 是 \(O(n^3)\) ，最后合并也是 \(O(n^3)\) 的，所以最终复杂度就是 \(O(n^3)\) 。

  • luogu P3246 [HNOI2016] 序列

    本题存在离线莫队做法，在线单 \(log\) 做法，甚至线性 \(RMQ\) 做法。

    这里提供一个离线扫描线做法。

    预处理出 \(a_i\) 左边第一个小于等于它的位置 \(L_i\) ，右边第一个小于它的位置 \(R_i\) 。那么如果不考虑询问边界，答案就是 \(\sum a_i(i-L_i)(R_i-i)\) ，考虑加上边界怎么办，就是对于所有 \(L_i\) 和 \(R_i\) 进行了截取。找出这些被截取的位置，减去它们原来的贡献，加上新的贡献即可。

    首先找到区间内的最小值位置 \(p\) ，显然 \(p\) 的两端都被截取，左半段只有左端可能被截取，右半段只有右端可能被截取。我们不妨拿左半段举例：对于一个询问 \([l,r]\) ，如果一个位置 \(i\) 满足 \(L_i ，那么就要减去它原来的贡献，加上 \(a_i(i-l+1)(R_i-i)\) ，观察到新的贡献形式是可以拆开维护的，分别维护 \(\sum a_i(i+1)(R_i-i)\) 和 \(\sum a_i(R_i-i)\) 即可。

    于是就可以简单的扫描线了。复杂度 \(O(nlogn)\) 。

  • luogu P17286 「IXOI R2」Horizon Blue

    刚刚那个题的升级版，加入了单点修改，并且强制在线。

    std给的是分治 + 线段树，我还没完全弄明白，先鸽了。这里提供一个分块做法。

    首先讲一下刚刚那个题的 \(O(n)\) 预处理 \(O(1)\) 查询的做法（注意原题的最小值这里改为了最大值，并且此题保证序列中的数两两不同）。

    我认为这里类似支配集的思想：

    我们设 \(f_i\) 表示所有以 \(i\) 为右端点的区间的最大值和，则 \(f_i=f_{pre_i}+a_i(i-pre_i)\) 这里 \(pre_i\) 表示 \(i\) 左边第一个比 \(i\) 大的值。同理 \(g_i\) 表示所有以 \(i\) 为左端点的区间的最大值和。

    这样对于一次查询 \([l,r]\) ，我们同样使用 \(RMQ\) 找到区间内最大值的位置 \(p\) ，然后直接输出答案 $ F(l,r)=a_p(p-l+1)(r-p+1)+\sum_{i=p+1}^r(f_i-f_p) +\sum_{i=l}^{p-1}(g_i-g_p)$ 即可，前缀和优化可以做到 \(O(1)\) 计算。

    好现在我们获得了线性处理所有询问 \(2\) 的方法，那么怎么处理操作 \(1\) 带来的影响呢？我们考虑将操作序列分块。注意这样仍然是在线的，我们分块是为了每次只考虑 \(B\) 个操作的影响。每进入一个新块，我们预处理出当前序列（经过了前面块的修改后的序列）的 \(f,g\) ，每次询问就先 \(O(1)\) 算出答案，再考虑把修改的贡献加进去。我们遍历这 \(O(B)\) 个有修改操作的“特殊点”，二分 + RMQ找出它左右两边第一个比它大的点（考虑进当前块的修改操作），设为 \([L,R]\) ，那么只有并且是所有包含于 \([L,R]\) 且跨过当前点的区间才会把最大值改变为该特殊点的值（这里之所以成立，是因为每个点的操作都是单调不降的）。\(O(1)\) 计算出这些点的贡献即可，即 \((a_i+y)(i-L)(R-i)+(F(L+1,R-1)-F(L+1,i-1)-F(i+1,R-1))\) 。

    使用 \(O(1)\) 的RMQ可以将复杂度降低到 \(O(m\sqrt n)\) ，可以用小常数的ST表或者分块来实现 \(O(1)\) RMQ。