常德建设网站公司,中山网络推广公司,网站设计制作价钱,海外市场推广做什么的二叉查找树 时间限制#xff1a;1 s 内存限制#xff1a;512 MB 【题目描述】 二叉查找树是一种特殊的二叉树#xff08;每个节点最多只有两个儿子的树#xff09;。树的每个节点上存有一个唯一的值#xff0c;并且满足#xff1a;这个节点的左子树内所有点的值都比这个…二叉查找树 时间限制1 s 内存限制512 MB 【题目描述】 二叉查找树是一种特殊的二叉树每个节点最多只有两个儿子的树。树的每个节点上存有一个唯一的值并且满足这个节点的左子树内所有点的值都比这个节点的值小且右子树内所有点的值都比这个节点的值要大。 对于一棵二叉查找树T我们可以将一个值为 x的新点插入 T中且保持树的性质。算法如下 需要将 x 插入树 T时执行 insert(x,T.root)。 现在有 N 个数需要插入一棵空树中。给定插入序列请在每个元素被插入之后输出所有节点的深度总和根的深度为 0。 【输入格式】 输入的第一行一个整数 n表示序列长度。 接下来一行n个数是序列中的数字这些数字是各不相同的在[1, n]区间。 【输出格式】 输出 n 行第 i 行整数表示第 i个数插入树后至这个节点的节点深度总和。 【样例输入】 8
3 5 1 6 8 7 2 4【样例输出】 0
1
2
4
7
11
13
15【数据规模与约定】 对于 50%的数据满足n ≤ 1000 对于100%的数据满足n ≤ 3 ∗ 1e5 【来源】 qbxt 2017.10.7 t1 我们可以发现这棵二叉搜索树构建完毕之后根节点总是比他的子树内任意一个节点先插入 而直接构造是n^2级别的我们需要知道有一种东西叫笛卡尔树其实就是一颗treap既满足二叉搜索树的性质又满足堆的性质对于任意一个节点有两个值key和fixkey满足二叉搜索树fix满足堆如果key是按大小顺序插入的那么我们可以在O(n)的时间内构造出这棵树那么我们就按题目中所给数字大小顺序插入fix值为其插入时间就可以构造出符合题目的那棵树了。(key和fix给定时可以唯一确定一棵树) 1 #includecstdio2 #define ll long long3 using namespace std;4 const int inf3e510;5 int fix[inf],n,fa[inf],dep[inf],a[inf];6 ll ans;7 int main()8 {9 scanf(%d,n);
10 for(int i1;in;i){
11 scanf(%d,a[i]);
12 fix[a[i]]i;
13 }
14 for(int i1;in;i){
15 int last0,fi-1;
16 while(fix[f]fix[i])lastf,ffa[f];
17 fa[i]f;
18 fa[last]i;
19 }
20 dep[0]-1;
21 for(int i1;in;i){
22 dep[a[i]]dep[fa[a[i]]]1;
23 ansdep[a[i]];
24 printf(%lld\n,ans);
25 }
26 return 0;
27 } View Code 转载于:https://www.cnblogs.com/hyghb/p/8228287.html
