可持久化线段树 思想 可持久化线段树的思想如下 建立多棵线段树，代表不同版本。 为了降低空间复杂度，每棵线段树只储存与上一棵不同的部分，结构并不完整。换句话说，每个节点都是先继承上个版本，如果自己的儿子信息被修改了，那么新建立一个节点代替自己。而对于根节点，无论修改是否改变了根节点的信息，根节点的版本都改变了，因此必须新建节点，同时也能代表版本。 任意两棵线段树都能相减得到一棵新线段

线段树上二分 用形式化的语言讲，线段树上二分求解的是这一类问题。 给定 \(L\)，找到一个 \(R \in [L,n]\) 满足 \[ f \Big( op\big([L,R-1]\big) \Big) = 1 \] \[ f\Big( op\big(R\big) \Big)=0 \] 其中 \(f\) 为某种合法性函数，\(op\) 是将区间信息合并为 \(f\) 能处理的信息的

关于为啥失踪这么久…… NOIP 挂了太多的分。 由于疫情就回家上网课去了。 文化课实在是令人厌倦，但是又对 OI 没啥信心了，所以就开始了大摸鱼时代。 期间几经辗转终于买到了新书《算法竞赛》，想着最后学点东西，结束 OI 生涯了。 可是文化课实在是过于恶心人，一句话不如 OI。 由于一些原因，我弃置了所有原有的 OJ 账号。 然后再次。 只不过我上学期是把自己的电脑放到机房里

分析 用 \(n\) 次 BFS 求出任意两点之间的距离。 枚举 \(b,c\)，预处理 \(p(b,0/1/2)\)，表示能到达 \(1\) 和 \(b\) 的最大/次大/第三大值，\(q(c,0/1/2)\) 同理。 那么接下来就是要求选出的两个点不等于 \(b,c\) 且不相等，是一个大分类讨论。 但是注意到最多 \(9\) 种搭配，所以只要求合法的最大值即可。 教训：不要上来

枚举极长横杠。 设 \(f(x,y)\) 为从 \((x,y)\) 最多同时向上向下延伸多少个白色格子。 对于每一行 \(x\)，直接处理两个黑色格子中间的部分，设为 \([l,r]\)，那么贡献为 \[ \sum_{y_1=l}^r \sum_{y_2=y_1+1}^r \min\{f(x,y_1),f(x,y_2)\} \] 考虑如果将 \(f(x,y)\) 递增排序，那么对于排

\(\texttt{analysis}\) 发现每条边 \((x,y)\) 的权值只可能是 \(a_x\)，\(a_y\)，\(m\)。 对于一个节点 \(x\)，与它相连的所有边权的中位数不超过 \(a_x\)，那么 \(deg_x\) 条边中，最多有 \(\lfloor \frac{deg_x}{2} \rfloor + 1\) 条边小于等于 \(a_x\)，也就是至多有 \(\lc

分析 按位贪心。 由于高位的 \(1\) 优于低位的所有 \(1\)，所以考虑一个过程check(x)，表示是否能够在保证更高位的 \(1\) 不会减少的情况下，使得当前这一位为 \(1\)。 设 \(f(i,j)\) 表示前 \(i\) 本书，划分成 \(j\) 段是否可行。 \[ f(i,j) = \operatorname{OR}_{k=0}^{i-1} f(k,j-1) \o

分析 首先让自己和协作者在多个不同的州演讲一定不优。 证明：反证法。假设更优，那么由于自己和协作者的演讲速度相同，所以在同样的时间里，让协作者为自己「加速」和分头演讲的总量是不变的。而让自己加速能够在更短的时间里得到正在演讲的那个州的票，矛盾。 其次，对于任意一个州，它的演讲时间只能为 \(A_i\)，\(B_i[B_i \neq -1]\)，\(0\)。这个是显然的。为了方便起见，分别称

杂题选讲 4. luogu8110 矩阵 分析 萌萌题。 \[ A^2_{i,j} = \sum_{i=k}^n A_{i,k} \cdot A_{k,j} = \sum_{k=1}^n a_ib_ka_kb_j = a_ib_j\Big( (\sum_{k=1}^n a_ib_i) = d\Big) \] \[ \sum_{i=1}^n \sum_{j=1}^n A^2_{i,

分析 显然 \(Z\) 函数。 由于在 \(Z\) 函数中考虑的是匹配串的后缀，所以从后往前考虑。 设 \(f_i\) 为考虑 \([i,n]\)，能够划分的最小段数，设 \(g_i\) 为匹配串的 \([i,n]\) 与模式串的 LCP 长度。 转是显然的。 \[ f_i = \min_{j \in [i+1,i+g_i]} \{ f_j \} + 1 \] 虽然 \(i+g