数据结构
(1).基础知识
需要掌握：数组，链表，队列，栈，堆
((1)) 队列：FIFO（先进先出）
((2)) 栈：FILO（先进后出）
(2).堆
浅谈堆
((1)).实现：二叉树
二叉树最简单的实现：一维数组
二叉树编号法：设当前的节点编号为i，则其左儿子(2i) ，右儿子(2i+1)
((2)).分类
大根堆：一个节点一定比它的两个儿子的权值大
（所以求最大值直接返回根节点）
小根堆：一个节点一定比它的两个儿子的权值小
（所以求最小值直接返回根节点）
((3)).基本操作
- 返回最值 ((max or min))
- 删除（堆顶元素）任意元素
- 插入一个元素
strcut Heap{
int n; //有n个数
int a[100010]; //这n个数存在了a[1~n];
inline int top{ //求最大值
return a[1];
}
inline void insert(int x){ //插入
a[++n]=x; //放到最后
int p=n;
while(p>1 && a[p]>a[p/2]) swap(a[p],a[p/2]),p/=2;
//p>1 保证不是根节点
//a[p]>a[p/2] -> 如果当前节点比其父节点值大，不满足大根堆的要求，交换
//直至合法为止
}
inline void delete(int q){
swap(a[q],a[n]);n--; //删除a[q]
int p=1;
while(p*2<=n){ //左儿子存在
int pp=2*p; //左儿子
if(pp+1<n &&a[pp+1]>a[pp]) pp++;
//如果右儿子也存在，且右儿子值比左儿子值大，指向右儿子
//如否，指向左儿子
//不管指向谁，都是较大的那个
if(a[p]<a[pp]){
swap(a[p],a[pp]);
p=pp;
}
}
}
};
(3).ST表
浅谈ST表
(ST)表是一种用于解决 (RMQ) （Range Minimum/Maximum Query,即区间最值查询）问题的算法
以最小值为例：
表示：令(f[i][j])表示从 (i) 开始 (2^j) 个数的最小值
则显然 (f[i][0]=a[i]);
转移：(f[i][j]=min(f[i][j-1],f[i+2^{j-1)}][j-1]));
解释：根据 (2^j=2^{j-1} + 2^{j-1})
(f[i][j-1]) -> 先从 (i) 数 (2^{j-1}) 个数
(f[i+2^{j-1}][j-1]) -> 现在的起始位置为上次走完 (2^{j-1}) 后的位置
故为(i+2^{j-1})，再走(2^{j-1})，故(f[i+2^{j-1}][j-1])
int main(){
cin>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=0;(1<<i)<=n;i++)
for(int j=(1<<i);j<(1<<(i+1));j++) //j从2^i~2^(i+1)
use[j]=i; //use[i] 表示用两个长度为use[i]的段盖住长度为i的段
for(int i=1;i<=n;i++) f[i][0]=a[i]; //初始化
for(int j=1;(1<<j)<=n;j++)
for(int i=1;(1<<i)<=n;i++)
f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
//1<<j表示2^j，指1左移j位，得到的结果在十进制下为2^j
for(int i=1;i<=m;i++){
int l,r;
cin>>l>>r; //左右端点
int len=r-l+1; //[l,r]长度
int j=use[len];
cout<<min(f[l][j],f[r-(1<<j)+1][j]);
}
}
(Practice):
(Problem 1)：给你 (N) 个数，求平均值最大的子区间
(Solution Problem 1)： 因为（从最大值开始）每加进来一个数平均值都会减小，所以其实答案就是数组里最大的那个数。
(Problem 2)：给你 (N) 个数，求(min(a_i,a_{i+1},...a_j) * |i-j|)的最大值 ((N<=10^5))
(Problem 3)：给定 (N) 个点，这 (N) 个点与 (N-1) 条边组成一个树。
有(M)次询问，每次询问给定(p1,p2)两点，问这两点之间的路径上有没有三个点，他们的点权可以构成一个三角形的三边。对于每一次询问，输出"YES"或"NO"
(Problem 4):
现有一个 (N*N) 的矩阵，其中有 (M) 个特殊点。
两个点的距离定义为它们的曼哈顿距离。
任意一个点的权值 指它到达每个特殊点的距离的最小值。
从 ((1,1)) 走到 ((n,n))，求经过的权值的最小值最大是多少
(Solution Problem 4)：“最小值最大” -> 二分
(4).单调队列
有单调性的队列，即单调递减或单调递增的队列。
浅谈单调队列
struct Monotone_queue{
int q[100010]; //存队列元素
int head=1;tail=0; //队头，队尾
void pop{ //Detele
head++;
}
void push(int x){ //Add
while(head<tail && q[tail]>x) tail--;
//队列尾部的数比插入的数大，插入后无法保证单调性
//tail-- -> 相当于实现把队列尾部数弹出，直到合法
q[++tail]=x;
}
}
(5).并查集
浅谈并查集
inline int find(int p){
if(p=fa[p]) return p;
//return fa[p]=find(fa[p]);
int x=find(fa[p]);
fa[p]=x;
return x;
}
inline void merge(int x,int y){
x=find(x);
y=find(y);
if(x==y) return;
fa[x]=y;
}
/*inline void merge(int x,int y){
fa[find(x)]=find(y);
}
*/