数据结构

我感觉将算法放到一个板子里面容易忘记自己学了什么,所以我以后单独开个专栏来记录算法知识点

OK,数据结构第一舞目前想学知识点:

1. 笛卡尔树
2. 线段树

笛卡尔树

笛卡尔树的结构主要是: 一个数字有两个属性:数列中的位置和数值,满足两个性质,将位置作为键值,是一颗BST树,对这颗树进行中序遍历,返回的就是这个序列的顺序(其实就是满足一个性质,节点的左孩子小于当前节点,节点的右孩子大于当前节点)

实现方法:

1. 当前插入节点 x, 根据 x 的 value 不断从单调栈中弹出节点(根据你需要的笛卡尔树需要满足小根堆还是大根堆的性质)

2. 最晚弹出的节点 y 以及y的整棵子树成为 x 的左子树

3. 假设 x 在 单调栈中还压着 z 节点, x 成为 z 的右孩子

4. 将节点 x 根据 value 加入单调栈

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
	ios::sync_with_stdio(false); cin.tie(0);
	int n;
	cin >> n;
	vector<int> p(n + 1, 0);
	for(int i = 1; i <= n; i++) cin >> p[i];
	deque<int> dq;
	vector<int> left(n + 1, 0);
	vector<int> right(n + 1, 0);
	for(int i = 1; i <= n; i++){
		int last = -1;
		while(!dq.empty() && p[i] <= p[dq.back()]){
			last = dq.back(); dq.pop_back();
		}
		if(last != -1){
			left[i] = last;
		}
		if(!dq.empty()){
			right[dq.back()] = i;
		}
		dq.push_back(i);
	}
}