L2-012 关于堆的判断

题目描述：

将一系列给定数字顺序插入一个初始为空的小顶堆q[]。随后判断一系列相关命题是否为真。命题分下列几种：

• x is the root：x是根结点；
• x and y are siblings：x和y是兄弟结点；
• x is the parent of y：x是y的父结点；
• x is a child of y：x是y的一个子结点。

思路：

手写堆，只需要一个插入操作即可

插入完了以后，我们开一个id数组记录数字在堆中出现的位置

• 判根节点：看看id[x]是不是等于1即可
• 判x是y的兄弟节点:id[x] / 2 == id[y] / 2 && x != y
• 判x是y的父节点：id[y] / 2 == x
• 判x是y的子节点：id[x] / 2 == y

因为存在负权值，所以我们记录id的时候给所有数+10000即可

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k, x, y;
int tot;
int q[MAX];
int id[MAX];
string s;

void push(int x){
    q[++tot] = x;
    int p = tot;
    while (p / 2 > 0 && q[p / 2] > q[p]) {
        swap(q[p / 2], q[p]);
        p /= 2;
    }
}

void work(){
    cin >> n >> m;
    for(int i = 1; i <= n; ++i){
        cin >> x;
        push(x);
    }
    for(int i = 1; i <= n; ++i){
        id[q[i] + 10001] = i;
    }
    for(int i = 1; i <= m; ++i){
        cin >> x;x = id[x + 10001];
        cin >> s;
        if(s == "and"){
            cin >> y;
            y = id[y + 10001];
            cin >> s >> s;
            if(x / 2 == y / 2 && x != y){
                cout << "T\n";
            }
            else cout << "F\n";
        }
        else{
            cin >> s;
            if(s == "a"){
                cin >> s >> s >> y;
                y = id[y + 10001];
                
                if(x != y && x / 2 == y)cout << "T\n";
                else cout << "F\n";
            }
            else {
                cin >> s;
                if(s == "root"){
                    if(x == 1)cout << "T\n";
                    else cout << "F\n";
                }
                else{
                    cin >> s >> y;
                    y = id[y + 10001];
                    if(y / 2 == x)cout << "T\n";
                    else cout << "F\n";
                }
            }
        }
    }
}


int main(){
    work();
    return 0;
}