FallenLeaf's Blog

Content：Data Structs Date：2025.7.17 内容 并查集 ST表 线段树 关于树状数组 一维树状数组 单点修改，区间查询 对于这一类最普通的树状数组，没有什么好说的，直接维护前缀和即可。 struct BIT { long long tr[N]; static int lowbit(int x) { return x & (-x); } void add(int pos, long long value) { for (int i = pos; i <= n; i += lowbit(i)) tr[i] += value; } long long query(int pos) { long long retval = 0; for (int i = pos; i > 0; i -= lowbit(i)) retval += tr[i]; return retval; }} ...

VJudge CodeForces 算法 欧拉序 线段树 思路 对于这道题考虑使用欧拉序的性质： 对于树上的每一个子树，在欧拉序上都有一个区间与之对应。 对于 (u,v)(u, v)(u,v) 的最近公共祖先，在欧拉序上表现为区间 [posu,posv][pos_u, pos_v][posu​,posv​] 内深度最浅的节点。 所以可以将原树转化为欧拉序，将树上问题转化为序列上的区间问题，就可以使用线段树解决。 由于题目要求树的直径，所以用线段树查找区间最值，找到点 (u,v)(u, v)(u,v) 的最近公共祖先 lcalcalca，则 dist(u,v)dist(u, v)dist(u,v) 可以表示为： dist(u,v)=depu+depv−2⋅deplca\large dist(u,v) = dep_u + dep_v - 2 \cdot dep_{lca} dist(u,v)=depu​+depv​−2⋅deplca​ 而直径就是 max⁡{dist(u,v)}\max\{dist(u, v)\}max{dist(u,v)}。 所以原题目的问题就转化为...

洛谷 VJudge 算法 线段树 思路 题目要求维护支持单点修改和查询区间最大子段和的数据结构。 考虑使用线段树维护。对于区间 [l1,r1],[l2,r2][l_1,r_1], [l_2,r_2][l1​,r1​],[l2​,r2​] ，合并后的最大子段和有一下三种情况： 区间 [l1,r1][l_1,r_1][l1​,r1​] 的最大子段和。 区间 [l2,r2][l_2,r_2][l2​,r2​] 的最大子段和。 跨过中间，区间 [l1,r1][l_1,r_1][l1​,r1​] 的右边部分和区间 [l2,r2][l_2,r_2][l2​,r2​] 的左边部分合并后的最大子段和。 所以线段树要维护的信息有四个： 区间和 区间最大子段和 区间左侧最大子段和。 区间右侧最大子段和。 对以上四个信息分别维护即可。 代码 #include <bits/stdc++.h>constexpr int N = 5e4 + 5;int n, m, op, l, r, arr[N];class SegmentTree { protected: cla...

Luogu 算法 线段树 数学推导（平均数，方差） 思路 区间操作，很容易想到线段树。 但是方差不好合并，考虑拆解： s2=1n∑i=1n(Ai−A‾)2=1n∑i=1n(Ai2−2⋅Ai2⋅A‾+A‾2)=1n(∑i=1nAi2−∑i=1n2⋅Ai2⋅A‾+∑i=1nA‾2)=1n(∑i=1nAi2−2⋅A‾⋅∑i=1nAi+nA‾2)\large \begin{aligned} s^2 &= \frac{1}{n} \sum_{i = 1}^{n} (A_i - \overline A)^2 \\ &= \frac{1}{n} \sum_{i = 1}^{n} (A_i^2 - 2 \cdot A_i^2 \cdot \overline A + \overline A^2) \\ &= \frac{1}{n} (\sum_{i = 1}^{n} A_i^2 - \sum_{i = 1}^{n} 2 \cdot A_i^2 \cdot \overline A + \sum_{i = 1}^{n} \overline A^2) \\ &...

VJudge CodeForcces 算法 数学（质因数分解，因数个数，进制） 思路 根据进制的知识，对于 kkk 进制而言，只有当 n mod ki=0n \bmod k^{i} = 0nmodki=0 时，kkk 进制意义下的第 iii 位才会为零。 由于 k≤1012k \le 10^{12}k≤1012，所以直接进行除法操作肯定不行，考虑将 kkk 质因数分解，对于 kkk 的每一个质因数分别考虑。设 k=∏i=0spiαIk = \prod_{i = 0}^{s} p_{i}^{\alpha_{I}}k=∏i=0s​piαI​​，n!=∏i=0spiβin! = \prod_{i = 0}^{s} p_{i}^{\beta_i}n!=∏i=0s​piβi​​。则 n!n!n! 在 kkk 进制下末尾 000 的个数为 min⁡i=0s⌊βiαi⌋\min_{i=0}^{s} \lfloor \frac{\beta_i}{\alpha_i} \rfloormini=0s​⌊αi​βi​​⌋ 。 代码 #include <bits/stdc++.h>us...

Luogu 算法 数学（素数筛，因子个数） 思路 对于原式做如下推导： 1x+1y=1n!x+yxy=1n!n!⋅(x+y)=xyn!⋅x+n!⋅y−xy=0xy−n!⋅x−n!⋅y=0\large \begin{aligned} \frac{1}{x} + \frac{1}{y} &= \frac{1}{n!} \\ \frac{x + y}{xy} &= \frac{1}{n!} \\ n! \cdot (x + y) &= xy \\ n! \cdot x + n! \cdot y - xy &= 0 \\ xy - n! \cdot x - n! \cdot y &= 0 \end{aligned} x1​+y1​xyx+y​n!⋅(x+y)n!⋅x+n!⋅y−xyxy−n!⋅x−n!⋅y​=n!1​=n!1​=xy=0=0​ 由上式联想到： (a−x)(b−x)→ab−ax−bx−X2\large (a - x) (b - x) \to ab - ax - bx - X^2 (a−x)(b−x)→ab−ax−bx−X2 比较...

Luogu 算法 搜索 思路 由于 n≤18n \le 18n≤18，可以考虑搜索。 定义 dfs(cur,a,b)dfs(cur, a, b)dfs(cur,a,b) 表示搜索到了第 curcurcur 头猪，使用了 aaa 条抛物线，前面还有 bbb 头猪为被击中。 对于一条抛物线 y=ax2+bx+cy=ax^{2}+bx+cy=ax2+bx+c，需要三个点确定其解析式。由于题目钦定了抛物线必定经过 (0,0)(0,0)(0,0)，所以还需要两个点。在前面为被击中的 bbb 头猪中选择一头与第 curcurcur 头猪配对。假设两头猪的坐标为 (x1,y1),(x2,y2)(x_{1}, y_{1}), (x_{2},y_{2})(x1​,y1​),(x2​,y2​)。则 {ax12+bx1=y1ax22+bx2=y2→{a=(y1x2−y2x1)x12x2−x1x22b=y1−x12ax1\begin{cases} a x_{1}^{2} + b x_{1} = y_{1} \\ a x_{2}^{2} + b x_{2} = y_{2} \\ \end{cases...

VJudge 洛谷 Codeforces 算法 贪心 思路 考虑特殊情况。当 m=1m=1m=1 时，问题转化为：给定 a0a_0a0​, 求删除最少元素使得对于任意的 iii，满足 Σj=0iaj≥0\Sigma_{j=0}^{i} a_{j} \ge 0Σj=0i​aj​≥0。 将特殊情况扩展到 m≤106m \le 10^6m≤106，即对于每一个给定的 a0a_0a0​，求解上述问题。 考虑贪心，即对于一个 iii，满足 Σj=0iaj<0\Sigma_{j=0}^{i} a_{j} < 0Σj=0i​aj​<0， 则必定删除前面最大的负数，才会使最后的结果最优.于是可以逆向思维，倒序遍历数组 aaa，维护一个大根堆(即维护绝对值最小的负数，对于每一个 ai<0a_{i} < 0ai​<0, 将其入队；对于每一个 ai≥0a_{i} \ge 0ai​≥0，用 aia_{i}ai​ 抵消堆顶元素，直到堆为空或 ai<0a_{i} < 0ai​<0。 最后将堆里的元素全部放入一个新数组，即这些负数在 a1→an...