都是典中典,我之前还不是很会。 简介 对于一颗正常的线段树,如果要支持所有版本都既可以访问又可以修改(完全可持久化),对于每个版本保存一颗线段树是不可接受的。 发现每次修改操作修改的点的个数只有 logn\log nlogn 个,...
ARC158C 题解
“かけがえのない日々を ここで 積みかさねて ひとつひとつ いまさらわかった”—— 《想いよひとつになれ》 题意简述 设 f(x)f(x)f(x) 为 xxx 的数字和。例如 f(158)=1+5+8=14f(158)=1+5+8=...
联通性相关
发现这部分学的最烂,稍微整理下。 强连通分量 定义 强连通的定义:有向图 GGG 强连通,当且仅当 GGG 的任意两个节点联通。 强连通分量(Strongly Connected Components,SCC)的定义是:极大的强连...
根号数据结构
很久之前写的烂尾笔记 根号数据结构 简介 顾名思义,复杂度含 O(n)O(\sqrt n)O(n) 的数据结构叫根号数据结构,一般都运用了分块和分值的思想。 分块 简介 分块的基本思想是,通过对原数据的适当划分,并在划分后的...
ABC290G 题解
“空高く舞う鳥へ かさねたハート”—— 《Jump up HIGH!!》 题意简述 有一颗深度为 DDD 的满 KKK 叉树,你需要剪掉一些边使其存在大小为 XXX 的联通分量,求最少剪掉的边的条数。 分析 考虑选择 所有 大小大...
P3730 莫队+值域分块题解
“生きる熱さを感じたいだけさ”—— 《スリリング・ワンウェイ》 莫队+值域分块题解 题意简述 查询区间内出现次数第k小的值的出现次数。 1≤N,M≤1051\leq N, M\leq 10^51≤N,M≤105 题目分析 这种 ...