题意解析

Treap（树堆）数据结构，用于维护一个基于字符串字典序和随机优先级的二叉搜索树。

解题思路

首先根据字符串键值对节点排序，确保插入后二叉树满足左子树键值 < 根节点键值 < 右子树键值的性质。插入时，通过比较节点优先级与父节点优先级，将优先级较高的节点上移，确保每个节点的优先级大于其子节点（大根堆性质）。此处实现简化了旋转操作，直接通过父节点指针调整，未实现标准的左旋 / 右旋。中序遍历（左 - 根 - 右）可按字典序输出所有节点，括号结构用于展示树的层级关系。

#include <iostream>
#include <cstdio>
#include <limits.h>
#include <algorithm>
#include <cstring>
using namespace std;

#define maxn 150
#define maxl 50050

struct node {
    char str[maxn];
    int pa, ls, rs;
    int pri;
};

bool operator <(node a, node b) {
    return strcmp(a.str, b.str) < 0;
}

node treap[maxl] = { 0 };

void insert(int i) {
    int j = i - 1;
    while (treap[j].pri < treap[i].pri) {
        j = treap[j].pa;
    }
    treap[i].ls = treap[j].rs;
    treap[j].rs = i;
    treap[i].pa = j;
}

void dscan(int k) {
    if (!k)
        return;
    printf("(");
    dscan(treap[k].ls);
    printf("%s/%d", treap[k].str, treap[k].pri);
    dscan(treap[k].rs);
    printf(")");
}

int main() {
    int n;
    while (scanf("%d", &n)) {
        if (!n)
            break;

        getchar();

        memset(treap, 0, sizeof(treap));

        for (int i = 1; i <= n; ++i) {
            cin.getline(treap[i].str, maxn, '/');

            scanf("%d", &treap[i].pri);
            getchar();
        }

        treap[0].pri = INT_MAX;

        sort(treap + 1, treap + n + 1);

        for (int i = 1; i <= n; ++i) {
            insert(i);
        }

        dscan(treap[0].rs);
        printf("\n");
    }
    return 0;
}