笛卡尔树

节点构成

key(通常是数组下标)val (数组的值)left, right (左右子树)

特点:

从 key 值来看, 他是一颗二叉搜索树.某个节点a的左后代节点的key都小于a的key,右后代节点的key都大于a的key从val 看, 他是一个(大)小根堆, a的val 值是后代中最(大)小的, 看你怎么建树

应用:

区间最值 : 如果把一个数组建造成一个笛卡尔树,那么 某个节点 a 和 a 的左右后代节点记作 {a}, 必然在数组上是连续的区间.参见特点一,{a} 的区间最值一定是a的val, 参见特点二.最深公共祖先: 两个节点 a,b 的最深公共祖先是, a-b区间内最值的位置.

A题:

判断两个数组a,b的最长前缀u和v满足: RMQ(u,l,r)=RMQ(v,l,r) 1≤l≤r≤m

(对于区间u和v, l-r范围内最小值的 indx 相等), 区间最值, 正是笛卡尔树应用的地方, 如果每个区间的最值位置是一样的,那么这两个笛卡尔树的形状一定相同.

如何判断两个前缀的笛卡尔树的形状?

建树,利用栈O(n)

自己解释不清楚

参考这个大佬

自己写了个模板,用node数组建树

int n, a[maxn]; struct node{ int key, val; int left = -1, right = -1; node(int k=0, int v=0, int l=-1, int r=-1):key(k), val(v), left(l), right(r){} } tree[maxn]; void dk_tree(int* a/*要建树的数组*/, int n/*数组大小*/, node* tree) { stack<int> s; while(!s.empty()) s.pop(); tree[0] = (node){0,-INF,-1,-1};//虚根,数组从1开始 s.push(0);//最小的虚根在栈底 for(int i = 1; i <= n; i++) { int p = s.top(); tree[i].val = a[i], tree[i].key = i; while(tree[p].val > a[i]) {//直到p <= 他,接在p的右子树,p原来的右子树接在他的左子树 s.pop(), p = s.top(); } s.push(i); //先把p的右子树接在他的左子树 tree[i].left = tree[p].right, tree[i].right = -1; //在把他接在p的右子树 tree[p].right = i; } } int main() { read(a); dk_tree(a, n, tree); }

回到A题

可以发现,建树过程中每个节点必然要进栈一次, 而进栈出栈的情况决定了这棵树的形状,于是,对于A题的两个数组, 每次处理完一个节点, 比较两个栈的大小即可判断两个栈进出栈情况是否一样,所以这道题不用建树就可以判断.

代码:

#include <cstdio> #include <iostream> #include <string> #include <queue> #include <cstring> #include <cmath> #include <stack> #include <algorithm> using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef long double LD; typedef pair<int, int> pii; #define FOR(i, a, b) for (int i = (a); i <= (b); i++) #define pb push_back #define f first #define s second #define lb lower_bound #define ub upper_bound //floor()ceil()round() LL gcd(LL a, LL b) { return b == 0 ? a : gcd(b, a%b);} void fast_io() {ios_base::sync_with_stdio(0); cin.tie(0);} const LD PI = 4*atan((LD)1), eps = 1e-8; const int INF = 0x3f3f3f3f; const LL maxn = 1e5+10, mod = 1e9+7; int n, a[maxn], b[maxn]; LL zjz() { int t1=0, t2=0; stack<int> s1, s2; while(!s1.empty()) s1.pop(); while(!s2.empty()) s2.pop(); FOR(i,1,n) { while( s1.size() && a[i] < a[s1.top()]) s1.pop(); while(s2.size() && b[i] < b[s2.top()]) s2.pop(); if(s1.size() != s2.size()) return i-1; s1.push(i), s2.push(i); } return n; } int main() { fast_io(); while(cin >> n && n) { FOR(i,1,n) cin >> a[i]; FOR(i,1,n) cin >> b[i]; cout << zjz() << endl; } return 0; }

转载于:https://www.cnblogs.com/rookiezjz/p/11212365.html

相关资源：数据结构—成绩单生成器