序列版本 给你长度为 nnn 的数组 aaa。一次操作将一个子区间上所有元素减 111。 求元素全变成 000 的最少操作数。 n≤105,ai≥0n \le 10^5, a_i \ge 0n≤105,ai​≥0。 原题链接：P1969 [NOIP 2013 提高组] 积木大赛、P5019 [NOIP 2018 提高组] 铺设道路、P3078 [USACO13MAR] Poker Hands

众所周知，块状链表实现平衡树是 O(nn)O(n\sqrt{n})O(nn​) 的，且不用一些手段卡不过加强版，那么有没有什么科技可以让块链达到 O(nlog⁡n)O(n \log n)O(nlogn) 呢？ 有的兄弟，有的。在 Python 的第三方库 Sorted Containers 里实现了一种块状链表，通过建索引树倍增优化查找过程，使得单次操作的复杂度降到了均摊 O(log⁡n)O(\l

众所周知，特殊角法是初中几何的降维打击。其在初中的主要体现为 12345 模型。本文对特殊角进一步探究，使之可以适应所有题型。 初步探究 这是本文发布前，笔者关于特殊系的一些探究。 角度 对边 临边 斜边 α\alphaα aaa bbb ccc α2\dfrac{\alpha}{2}2α​ c−b\sqrt{c-b}c−b​ c+b\sqrt{c+b}c+b​ 2c\sqrt{

感觉将主席树的很多教程都不讲权值线段树，然后本蒟蒻花了半天时间理解主席树维护的线段树和区间线段树有什么区别。 权值线段树 普通线段树解决的问题： 对序列上一段区间做修改； 对序列上一段区间查询信息。 而权值线段树把这个序列变成了值域，相当于维护原序列的出现次数。那么权值线段树对值域做维护，自然也就能支持对值域的操作。我造了一个板子题 SPN D-Struct 02，下面写写这题题解： 对值域建

介绍 基环树，一般有 nnn 个点 nnn 条边的无向连通图，比如： 环用红色标出，可以看到基环树就是一个环上挂了若干子树。特别地，基环树也可以退化为一个单环。 解决基环树的问题有两种思路： 对环上每棵子树先处理，再处理环，最后合并答案； 将基环树拆成树 + 一条边，即断环为链。 因此，基环树问题需要树上问题和环上问题的良好基础。 例题 P8655 [蓝桥杯 2017 国 B] 发现环 【模

字符串哈希 字符串哈希一般用于快速判断两个串是否相同。 常用的方法：对于字符串 sss，其哈希值为 (∑i=1nsi×bn−i) mod m(\sum_{i=1}^{n} s_i \times b^{n-i}) \bmod m (i=1∑n​si​×bn−i)modm 只需要 O(n)O(n)O(n) 计算。 一般 nnn 达到 10610^6106 时 mmm 需要开到 101510^{15}1

前言 AVL 树是工程中常用的平衡树，其在大量查询方面具有优势。然而，AVL 树在 OI 中却没有特别地位。 笔者认为，AVL 树原理简单，比 OI 常用平衡树快很多，码量也不是很大。本文探究 AVL 树在 OI 领域的扩展应用。 AVL 树原理 AVL 的每个节点维护一个 high 域，表示子树的高度。AVL 需要维护 ∣highl−highr∣≤1|high_l-high_r|\le 1∣hi

背景 之前周练考了，把叉乘乘反了，-9pts。 据说不咋考了，不过还是写一下，期末考 rp++ 触底反弹（ 例题 借用周练题。 如图，y=−6xy=-\dfrac{6}{x}y=−x6​ 上有两点 A(−2,3),B(6,−1)A(-2,3),B(6,-1)A(−2,3),B(6,−1)，若点 PPP 在 y=−6xy=-\dfrac{6}{x}y=−x6​ 上，且 S△APB=8S_{\tria

Example 0 求 a±b\sqrt{a \pm \sqrt{b}}a±b​​ 的值和判别式。 注意到，要把这个根号开出来，可以把根号里面化为完全平方式。于是作换元，令 a=m2+n2,b=2mna=m^2+n^2, \sqrt{b}=2mn a=m2+n2,b​=2mn 则 原式=m2+n2±2mn=(m±n)2=m±n\text{原式} = \sqrt{m^2+n^2 \pm 2mn}=\

最近 % 你赛出了好几个这样的问题。 算法思想 将询问离线，按一个端点排序，用另一维作扫描线统计答案。统计时，按题目选择权值 / 序列树状数组或线段树，复杂度为 O(nlog⁡n)O(n\log n)O(nlogn) 级别。 例题 P10814 【模板】离线二维数点 板子题。注意到 ansl,r=ans1,r−ans1,l−1ans_{l,r}=ans_{1,r}-ans_{1,l-1}ansl,