整理的笔记 @AC君 求顶置
2024-07-27 16:22:54
发布于：浙江
21阅读
0回复
0点赞
ST:
F[i][j] 表示区间 [i,i+2^(j-1)] 区间的差值 区间长度为2^j
F[i][j] = max(F[i][j-1],F[i+2^(j-1)][j-1])
区间最值 F[i][j] 区间长度 2^j
区间最值 F[i][j-1] 区间长度 2^(j-1)
a[i] ... a[i+2^(j-1)-1] a[i+2^(j-1)] ... a[i+2^(-1)] ...
区间最值 F[i+2^(j-1)][j-1] 区间长度 2^(j-1)
void St_create() {
for (int i = 1;i <= n;i ++) F[i][0] = a[i];
int k = log2(n);
for (int j = 1;i <= k;j ++) {
for (int i = 1;i <= n;i ++) {
F[i][j] = max(F[i][j - 1], F[i + (1 << (j - 1))][j - 1]);
F[i][j] = min(F[i][j - 1], F[i + (1 << (j - 1))][j - 1]);
}
}
}
k = florr(log2(n));
#include <bits/stdc++.h>
using namespace std;
int mx_f[500005][30];
int mi_f[500005][30];
int n,q,a[1000005];
void createmax() {
for (int i = 1;i <= n;i ++) mx_f[i][0] = a[i];
int k = log2(n); // 取q的最大值
for (int j = 1;j <= k;j ++) {
for (int i = 1;i <= n - (1 << j) + 1;i ++) {
mx_f[i][j] = min(mx_f[i][j-1],mx_f[i + (1 << j - 1)][k]);
}
}
}
void createmin() {
for (int i = 1;i <= n;i ++) mi_f[i][0] = a[i];
int k = log2(n); // 取q的最大值
for (int j = 1;j <= k;j ++) {
for (int i = 1;i <= n - (1 << j) + 1;i ++) {
mi_f[i][j] = min(mi_f[i][j-1],mi_f[i + (1 << j - 1)][k]);
}
}
}
int Queue(int l,int r) {
// 最大值与最小值返回差值
int k = log2(r - l + 1);
int mx = max(mx_f[l][k],mx_f[r - (l << k) + 1][k]);
int mi = min(mi_f[l][k],mi_f[r - (l << k) + 1][k]);
return mx - mi;
}
int main() {
cin >> n >> q;
for (int i = 1;i <= n;i ++) cin >> a[i];
createmax();
createmin();
while (q --) {
int l,r;
cin >> l >> r;
cout << Queue(l,r) << "\n";
}
return 0;
}
完全二叉树 :
前序: 根左右
中序: 左根右
后序: 左右根
除第k层外其他的结点总数达最大值，且k层结点数小于等于2^(k-1)并靠左
侧连续 称为完全二叉树
n为奇数时 完全二叉树中没有度为1的结点 此时 n = n0 + n2;
n为偶数时 完全二叉树中只有一个度为1的结点 此时 n = n0 + 1 + n2;
具有n(n >= 0) floor(log2(n)) + 1;
n-3+1
log = 2
2
左孩子 编号2*i (2 * i <= n);
右孩子 标号2*i+1 (2*i+1 <= n);
1
/ \
2 3
/ \ /
4 5 6
DataType tree[N];
tree[i] , tree[2 * i] , tree[2 * i + 1];
//父结点 左孩子 右孩子
与根节点的通路叫做路径
第L层结点到根节点的路径长度为L-1;
层数 路径长度 L-1
1 0 9
2 1 / \
3 2 6 3
^ / \
| 2*1=2-> 1 5
二叉搜索树:
Binary Search Tree -> BST 二叉搜索树 -> 二分搜索树 log2(n); o(n)
左子树上所有结点的值都小于它的根节点(若左子树不为空)
右子树上所有的结点的值都大于它的根节点(右子树不为空)
他的左右结子都是二叉搜索树
拓扑排序:（英语:Topological sorting),拓扑排序要解释的问题给一个有向无环图(DAG:边是有向的 没有形成成闭环)的所有节点排序
AVO 网: 顶点表示活动 有向边表示活动之间的优先制关系 (u,v) 表示活动u必须先于v进行 称这种有向图为顶点表示后动的网 简称
AOV 网 AVO网同时也是有向无环图(DVA)
动态规划:
是一种表格处理法 或者记忆递归法 在对问题求解时 通过把原问题分解为相对简单的
子问题的方式 求解复杂问题的一种方法
归并排序 快速排序 (分治) 大问题拆解成小问题 good() n -> 小问题
1 2 3 4 5 6 7 8 9 子问题独立
分治思想 ————- ———— 让原本的问题差分成答案时
---------> l mid r (l + r) >> 1; 差分
1.确定状态(读题);
2.划分阶段(规划);
3.确定转移方程(动态);
a[i] = min(a[i-1],min(a[i-5],a[i-11]))+1;
区间DP属于线段DP的一种 以区间长度作为DP的阶段 以区间的左右作为端点作为
状态的维度 一个状态通常由被他包含且比它更小的区间状态转移而来
有帮助，赞一个