题意：
每个节点有两个信息：string值和r优先级。要求构建一个Treap并且任意节点的string和r都是唯一的。最后按要求输出该Treap的序列。
题解：
直接写蓝书的Treap会超时，有种笛卡尔树的Treap可以写。（暂时还没看）
这里用RMQ递归写。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>using namespace std;const int maxn =50011;
int n;
int dmax[maxn][20];
struct node
{char v[222];int r;bool operator < (const node& a)const{return strcmp(v,a.v)<0;}
}ns[maxn];int maxv(int i,int j)
{if(ns[i].r>ns[j].r)return i;return j;
}void initmax()
{for(int i=1;i<=n;i++)dmax[i][0]=i;for(int j=1;(1<<j)<=n;j++)for(int i=1;i+(1<<j)-1<=n;i++)dmax[i][j] = maxv(dmax[i][j-1],dmax[i+(1<<(j-1))][j-1]);
}
int getmax(int l,int r)
{int k=0;while((1<<(k+1))<=r-l+1)k++;return maxv(dmax[l][k],dmax[r-(1<<k)+1][k]);
}void solve(int l,int r)
{if(l<=r){int m=getmax(l,r);printf("(");solve(l,m-1);///左边满足值小（实现排序printf("%s/%d",ns[m].v,ns[m].r);solve(m+1,r);///右边满足值大printf(")");}
}int main()
{char str[111];while(cin>>n&&n){for(int i=1;i<=n;i++){scanf(" %[^/]/%d",ns[i].v,&ns[i].r);}sort(ns+1,ns+1+n);initmax();solve(1,n);puts("");}
}笛卡尔树实现：
#include <iostream>
#include <string.h>
#include <algorithm>
#include <stdio.h>using namespace std;
const int N=500010;
const int INF=~0U>>1;struct node
{int fix;int pre,l,r;char str[10];void clear(){pre=l=r=0;}bool operator < (node t) const{return strcmp(str,t.str)<0;}
};node T[N];void Init(int n)
{for(int i=0; i<=n; i++)T[i].clear();T[0].fix=INF;
}int Build(int n)
{for(int i=1; i<=n; i++){int j=i-1;while(T[j].fix<T[i].fix)j=T[j].pre;T[i].l=T[j].r;T[j].r=i;T[i].pre=j;}return T[0].r;
}void dfs(int cur)
{if(cur==0) return;printf("(");dfs(T[cur].l);printf("%s/%d",T[cur].str,T[cur].fix);dfs(T[cur].r);printf(")");
}int main()
{int n;char str[105];while(scanf("%d",&n),n){Init(n);for(int i=1; i<=n; i++){scanf("%s",str);sscanf(str,"%[^/]/%d",T[i].str,&T[i].fix);}sort(T+1,T+n+1);int root=Build(n);dfs(root);puts("");}return 0;
}