并查集操作： 将两个集合合并 询问两个元素是否在一个集合中 暴力算法：合并$O(n)$，查询$O(1)$ 并查集： 基本原理：每个集合用一棵树来表示，树根的编号就是整个集合的编号。每个节点用$fa$数组存储父节点 问题1：如何判断树根:fa[x]...

平衡树BST(Binary Search Tree):二叉搜索树满足： 当前节点的左子树中的任何一个点的权值$<$当前节点的权值 当前节点的右子树中的任何一个点的权值$>$当前节点的权值 一般保证无重复权值，若有，可以在每个节点上记录...

常用STLvector变长数组（数组长度变化），倍增思想 初始化: 123vector<int>a;//定义一个普通vectorvector<int>a(10);//定义一个长度为10的vectorvector<int&...

差分作用：快速进行区间修改 给定数列$a$,构造数列$b$使得 $a_k=\sum_{\substack{1\le i\le k }} b_i$,则$b$是$a$的差分数组，$a$是$b$的前缀和数组，前缀和与差分互为逆运算 $b[i]&#...

堆操作： 插入一个数 求集合中的最大(小)值 删除集合的最大(小)值 删除任意一个元素 修改任意一个元素 以下以小根堆(根节点为最小值为例) 基本结构：二叉树 存储：用一个数组$heap$存储二叉树，$size$表示数组中元素的个数，$heap[...

基础优化技巧三分三分用来解决求单峰函数的极值点的问题。 单峰函数：在所考虑的区间中只有一个极值点的函数。 例题：[洛谷P3382 三分](P3382 三分) 三分题目背景本题可能存在严重精度问题，部分数据下难以通过。本题数据较水，仅供参考。 题目描述...

哈希表作用：类似离散化，将值域较大的一些数映射进较小的范围中，并快速查询是否存在 一般可以用取模运算来映射，取模时最好取质数 注意：c++取模时会出现负数，所以取模后加上$mod$再次取模即可 若重复，解决方法： 拉链法：利用链表存储重复元素 1...

双指针通用模板： 1234for(int i=1,j=1;i<=n;i++){ while(j<i&&check(i,j))j++; //每到题目的具体逻辑} 核心思想: 将$O(n^2)...

单调队列和单调栈单调队列应用：滑动窗口中的最大（最小值） 例：给定一个数列$a$，窗口的长度$k$，求滑动窗口的最小值和最大值 分析：以最大值为例：用队列存储当前窗口的值，保证队头是最大值，每次滑动窗口时先判断队头是否过期，若过期，则弹出队头，然后从...

区间合并作用：快速将几个有交集的区间合并成一个区间 方法： 按区间左端点排序 从左到右扫描区间： 若当前区间与后面的区间都没有交集，记录答案 若当前区间包含下一个区间，继续判断后面 若当前区间与下一个区间相交，则当前区间的右端点变为下个区间的右端...