笛卡儿树

2024-08-13

通过单调栈建立笛卡儿树,快速求解区间最值问题

#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;
}