butaihuia

摘要： 前言 关于树状数组是什么，我在之前的blog里写过 树状数组是什么? 先敲出一个框架先之后我将慢慢填充 树状数组的基础操作 基本操作 一、lowbits操作 所有操作的高速公路，用来连接树状数组中两个区间 点击查看代码 int lowbits(int x){ return x&-x; } 二、pus 阅读全文

摘要： 前言 学习一个知识点最基本是了解这个算法是什么，用来解决什么问题，怎么写这个算法，以及这个算法本质是什么 ST表的本质 构建时：它是 倍增 dp 。 查询时: 它是 重叠覆盖 。 什么时候可以用? 当一个序列满足以下性质时用ST表，用来解决； 可重复贡献 重复运算的区域不影响最后的答案 单调性 运算 阅读全文

摘要： 前言 并查集链接 关于并查集的更多知识点 拓展域并查集 扩展域并查集的本质就是用空间换逻辑清晰度。它将“节点与节点之间复杂的相对关系”，转化为“不同状态节点之间的绝对连通关系”。 食物链 点击查看代码 #include <bits/stdc++.h> using namespace std; #de 阅读全文

摘要： 并查集 三个字概括:找老大 1. 核心定义 一种用来高效管理“元素分组”的数据结构，专门处理“不相交集合”的合并及查询问题。 2. 两个动作 查 (Find) —— 找老大： 递归寻找当前元素的“根节点”（代表元素）。 并 (Union) —— 认干爹： 判断两个元素是否在同一个集合。如果不是，让一 阅读全文

摘要： 前言 比赛的时候只写了A~E后面结束后补，比赛链接:Atcoder 441 致力于把题目用通俗的语言翻译出来，让新人也能看懂 A 只要X Y范围在 (P,Q) 和 (P+99,Q+99)范围之间就成立 B 只要分成两个集合A,B 字符串中每一个字符都去匹配一下集合A,B就行了 C 题目人话: 有 N 阅读全文

摘要： 原题链接 区间修改 参考文献 董晓代码 @目录前言一、树状数组树状数组与线段树的区别树状数组单点修改二、lowbit()实现传递点连接lowbit()的定义为什么要用 lowbit() ？三、树状数组里的差分为什么用差分？树状数组与差分结合四、代码分析ac代码逐步分析输入数据add ( ) 函数qu 阅读全文

摘要： 原题链接洛谷提高组-火柴排队 分析 这题我是用离散化，数组映射(数据处理办法)，归并排序优化逆序对 写的。 关于（ai-bi）的平方 求和可以理解为 a组火柴和b组火柴 相对位置相等时 这个和最小 竟然有相对位置了就逃不了离散化数组了 对于求相邻交换次数，是不是很像冒泡排序。这时候就要引入逆序对了。 阅读全文

摘要： 题目 当一根长度为 L 的细棒被加热 n 度时，它会膨胀到新的长度 L'=（1+nC）L，其中 C 是热膨胀系数。 当一根细棒安装在两个实心壁上然后加热时，它会膨胀并呈现出圆段的形状，原来的棒是该段的弦。 您的任务是计算杆中心位移的距离。 输入 输入包含多行。每行输入包含三个非负数：杆的初始长度（以 阅读全文