摘要：
何为树状数组？ 首先，树状数组是用来维护序列的前缀和的。 其次，我们要知道树状数组是如何将大区间拆分成一堆小区间的。 比如 \(7 = 111_{(2)}\)，我们可以将其拆分为 \([1,4], [5, 6], [7, 7]\)，再比如 \(12 = 1100_{2}\)，我们可以将其拆分为 \( 阅读全文
posted @ 2024-12-15 11:16
はなこくん
阅读(59)
评论(0)
推荐(0)
摘要：
0x21 树与图的遍历 164. 可达性统计 令 \(f[x]\) 表示从 \(x\) 出发可到达点的集合，那么 \(f[x] = (\cup f[y]) \cup x\)（存在边 \((x, y)\)）。所以我们可以使用拓扑排序，倒着拓扑序进行计算。处理这个集合我们可以想到二进制压缩，但是一般二进 阅读全文
posted @ 2024-12-15 11:06
はなこくん
阅读(24)
评论(0)
推荐(0)
摘要：
0x11 栈 栈的运用 AcWing41. 包含min函数的栈 用一个辅助栈存所有可能成为答案的值，即维护两个栈，一个栈正常存，另一个栈存所有时刻的最小值。具体维护时如果新加入的值比辅助栈的栈顶小，就将它加入辅助栈，删除时判断两个栈栈顶是否相等，如果相等就让辅助栈栈顶出栈。 class MinSta 阅读全文
posted @ 2024-12-15 11:06
はなこくん
阅读(44)
评论(0)
推荐(0)
摘要：
0x01 位运算 AcWing89.a^b 快速幂模板题。 令 \(k\) 为 \(b\) 在二进制下的位数，\(t_i\) 为 \(b\) 在二进制下的第 \(i\) 位。 则 \(b = t_{k - 1} {2^{k - 1}} + t_{k - 2} 2 ^ {k - 2} + ... + 阅读全文
posted @ 2024-12-15 11:04
はなこくん
阅读(53)
评论(0)
推荐(0)
浙公网安备 33010602011771号