通过单调栈建立笛卡儿树,快速求解区间最值问题
#include <bits/stdc++.h>
#define io cin.tie(0), cout.tie(0), ios::sync_with_stdio(false)
#define LL long long
#define ULL unsigned long long
#define EPS 1e-8
#define INF 0x7fffffff
#define SUB -INF - 1
using namespace std;
const int N = 50005;
struct Node
{
char s[100];
int ls, rs, fa, pri;
friend bool operator<(const Node &a, const Node &b)
{
return strcmp(a.s, b.s) < 0;
}
} t[N];
void buildTree(int n)
{
for (int i = 1; i <= n; i++)
{
int pos = i - 1;
while (t[pos].pri < t[i].pri)
pos = t[pos].fa;
t[i].ls = t[pos].rs;
t[t[i].ls].fa = i;
t[pos].rs = i;
t[i].fa = pos;
}
}
void inorder(int x)
{
if (x == 0)
return;
printf("(");
inorder(t[x].ls);
printf("%s/%d", t[x].s, t[x].pri);
inorder(t[x].rs);
printf(")");
}
int main()
{
int n;
while (scanf("%d", &n), n)
{
for (int i = 1; i <= n; i++)
{
t[i].ls = t[i].rs = t[i].fa = 0;
scanf(" %[^/]/%d", t[i].s, &t[i].pri);
}
t[0].ls = t[0].rs = t[0].fa = 0;
t[0].pri = INF;
sort(t + 1, t + 1 + n);
buildTree(n);
inorder(t[0].rs);
printf("\n");
}
return 0;
}