前言 这个东西还挺神秘的，遂写一篇来说道。 高维前缀和一般解决以下问题： 对于所有的 S,0≤S<2nS,0\leq S<2^nS,0≤S<2n，求出 ∑subS⊆Saj\sum_{subS\sube S}a_j∑subS⊆S​aj​ 显然，如果对每一个 iii 都单独枚举子集，复杂度为 O(3n)O(3^n)O(3n)。而使用高维前缀和的复杂度可以到 O(n⋅2n)O(n\

link T3 desu. 怎么都是版题（） 原式子非常难看，不妨令 wi=∑k=1sumibaikw_i=\sum\limits_{k=1}^{sum_i}b_{a_{i_k}}wi​=k=1∑sumi​​baik​​​，原来的 www 改为 WWW。 可以发现这道题本质上是一个三维偏序，能从 jjj 转移到 iii 的条件为： {j<iW+wj≥wiSj⊆Si\begin{cases}

link T4 desu. vj 给定长度为 nnn 的序列 a1,a2,…,ana_1, a_2, \dots, a_na1​,a2​,…,an​（1≤ai≤n1 \le a_i \le n1≤ai​≤n），qqq 次操作： 1 l r：将区间 [l,r][l, r][l,r] 循环右移一位。即 ara_rar​ 移到 ala_lal​，其余元素依次右移 2 l r k：询问区间 [l,r]

link T2 desu. T1 太简单了没写 一眼莫队是真的。 不过这里有个小细节：拿到这道题的时候考虑的莫队是只增不减的回滚莫队，但其实这样复杂度会假。 为什么？考虑只增不减的 mexmexmex 怎么写 1234while(l<nowl){ ++tong[a[--nowl]]; while(tong[mex]) ++mex;} 你可知道这是回滚莫队。 假

link T3 desu. translated ver 好玩且 Educational 的题。 引用自 https://www.luogu.com.cn/article/tl6zx3q0 和 https://www.luogu.com.cn/article/mh3i34s3。有修改。 首先先分析下这个“最大前缀和”，按照最朴素的思路就是扫一遍每个前缀，然后记录一下当前的 前缀和 sss 与前面

link T2 desu 宫殿是 R×CR \times CR×C 的矩阵，有 NNN 个藏宝宫室，每间藏宝宫室有一扇传送门，类型为： 横天门：可传送到同行的任一宫室 纵霓门：可传送到同列的任一宫室 任意门：可传送到周围 8 格中任一存在的宫室 Henry 可以用便携门从任意宫室进入，在任意宫室结束，但只允许进出一次。宫内传送门可无限次使用，宫室可重复访问。 目标：安排一条路线，使经过的不同

link T1 desu 我去我怎么连这么简单的差分都没有想到（） 显然差分之后就变成了选取一正一负两个数抵消。这里只考虑 2∼n2\sim n2∼n 的差分数组。 那么令正数的和为 upupup，负数的和的相反数为 lololo，那么操作次数即为 max⁡(up,lo)\max(up,lo)max(up,lo)。 这其中的 min⁡(up,lo)\min(up,lo)min(up,lo) 次用于

link T3 desu 这道题有两种做法：分块和 LCT。LCT 很无脑，这里只讲分块。 先对整个数组分块，块长取 n\sqrt nn​。 分完块后维护两个东西： jumpc[i]：计算每个点跳出这个块需要多少步 jumpp[i]：计算每个点跳出这个块会去到哪里 显然的，计算答案只需要跳 n\sqrt nn​ 个块即可。主要讲一下 update 操作。 我们考虑建出每个块内弹力器往下

link T2 desu 懒得写，贴别人的算了。 随机化：link sub 确定性（类折半搜索）：link，没写（）

link T1 desu 这里给一个和其他题解不一样的建树思路。 显然我们可以发现，在某个人 xxx 成为被打败的对象之前，他是不断收集其他人的奖牌的。 这启示我们考虑将这些其他人的奖牌一起全部临时挂载到 xxx 上，包括本轮最新获得的奖牌也挂到 xxx 上。 然后等有某个 zzz 打败了 xxx 时，再新建一个点 ppp，把 xxx 下的点真正给到 ppp。然后把 ppp 挂给 zzz。 那么这