样例输入:
5 4
46 23 26 24 10
24 is the root
26 and 23 are siblings
46 is the parent of 23
23 is a child of 10
样例输出:
F
T
F
T
分析:这个话题实际上有点歧义,因为他给出的x和y是特定的值,但它不解释堆中的数字是否可以重复,所以很容易引起歧义,但因为他只根据相同的值来判断关系,所以默认情况下没有相同的元素。然后我们可以直接模拟小根堆,每次把当前元素放在最后,然后操作堆,然后映射排序的每个位置的值,包括mp[i]对于记录值为i的元素的位置,我们根据位置判断节点之间的关系,剩下的是字符串操作,详见代码:
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
const int N=2e4 10;
int a[N];
map<int,int> mp;
void up(int x)///x是下标
{
while(x!=1&&a[x>>1]>a[x])
{
swap(a[x>>1],a[x]);
x>>=1;
}
}
int main()
{
int n,m;
cin>>n>>m;
int root=0x3f3f3f3f;
for(int i=1;i<=n;i )
{
scanf("%d",&a[i]);
root=min(root,a[i]);
up(i);
}
for(int i=1;i<=n;i )
mp[a[i]]=i;
int x,y;
string s;
for(int i=1;i<=m;i )
{
cin>>x>>s;
if(s[0]=="a")
{
cin>>y>>s>>s;
if((mp[x]>>1)==(mp[y]>>1)) puts("T");
else puts("F");
}
else
{
cin>>s>>s;
if(s[0]=="r")
{
if(x==root) puts("T");
else puts("F");
}
else if(s[0]=="p")
{
cin>>s>>y;
if(mp[x]==(mp[y]>>1)) puts("T");
else puts("F");
}
else
{
cin>>s>>y;
if(mp[y]==(mp[x]>>1)) puts("T");
else puts("F");
}
}
}
return 0;
}
文章为作者独立观点,不代表股票配资公司观点