三分钟学会Treap

NC230366. 三分钟学会Treap

描述

ly哥哥正在学习一种叫treap的平衡树，它维护了两种权值 $a_i$ 和 $b_i$ 。
treap满足以下性质：

1.对于树中的每一个节点 $x$ ，如果其左儿子 $lsonx$ 存在则总有 $a_{lsonx}<a_{x}$ ，如果其右儿子 $rsonx$ 存在则总有 $a_x<a_{rsonx}$ 。
2.对于树中的每一个节点 $x$ ，如果其左儿子 $lsonx$ 存在则总有 $b_{lsonx}<b_x$ ，如果其右儿子 $rsonx$ 存在则总有 $b_x>b_{rsonx}$ 。

知道了这些之后，ly哥哥在三分钟内证明了在 $b_i$ 随机时treap期望深度为 $\log n$ 并且独立码出了treap的代码并且通过了模板题。
你不需要像ly哥哥那么厉害，你只要告诉我 $n$ 个节点（编号为 $1\sim n$ )构成的treap中 $m$ 个节点的父亲。

输入描述

输入的第一行是一个整数，表示这颗treap由个节点构成。
接下来一行有个整数代表第个数代表编号为节点的。
接下来一行有个整数代表第个数代表编号为节点的，保证随机。
数据保证和没有重复

接下来一行是一个正整数，表示询问的个数。
接下来行每一行是一个正整数，表示询问编号为的节点的父亲。

输出描述

行，第行输出对应询问的节点的父亲，如果询问节点没有父亲则输出。

示例1

输入:

5
9 4 5 -10 -9
5 -3 -10 -2 1
3
2
4
1

输出:

5
5
0

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C++ 解法, 执行用时: 617ms, 内存消耗: 22776K, 提交时间: 2021-12-02 14:56:33

#include<bits/stdc++.h>
using namespace std;
#define N 1000001
int n,m,x,fa[N];
struct dd
{
	int a,b,id;
}t[N];
bool cmp(dd a,dd b)
{
	return a.a<b.a;
}
void build(int l,int r,int x)
{
	if(l>r)
	return;
	int ma=-1e9,root;
	for(int i=l;i<=r;i++)
	{
		if(t[i].b>ma)
		{
			ma=t[i].b;
			root=i;
		}
	}
	fa[t[root].id]=x;
	build(l,root-1,t[root].id);
	build(root+1,r,t[root].id);
	return;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&t[i].a);
		t[i].id=i;
	}
	for(int i=1;i<=n;i++)
	scanf("%d",&t[i].b);
	sort(t+1,t+n+1,cmp);
	build(1,n,0);
	scanf("%d",&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d",&x);
		printf("%d\n",fa[x]);
	}
}

上一题

下一题

详情