Martian148's blog Martian148's blog
首页
  • ICPC 算法笔记
  • ICPC 算法题解
  • 体系结构
  • 高等数学
  • 线性代数
  • 概率论与数理统计
  • 具体数学
  • Martian148的奇思妙想
  • 游记
  • 通识课笔记
关于
  • useful 网站
  • 友情链接
  • 分类
  • 归档

Martian148

一只热爱文科的理科生
首页
  • ICPC 算法笔记
  • ICPC 算法题解
  • 体系结构
  • 高等数学
  • 线性代数
  • 概率论与数理统计
  • 具体数学
  • Martian148的奇思妙想
  • 游记
  • 通识课笔记
关于
  • useful 网站
  • 友情链接
  • 分类
  • 归档
  • 线上赛板子(实时更新)
  • 数据结构

    • 堆
    • 并查集
    • 树状数组
    • 分块
    • 树相关
    • 线段树
    • 平衡树
    • 树链剖分
    • LCT
    • 最近公共祖先
    • 虚树
    • 树分治
    • K-D Tree
    • 笛卡尔树
      • 珂朵莉树
    • 数学

    • 计算几何

    • 动态规划

    • 图论

    • 字符串

    • 杂项

    • 算法笔记
    • 数据结构
    martian148
    2024-09-03
    目录

    笛卡尔树

    Treap 树的每个节点有两个属性,键值和优先级

    笛卡尔树是一种特殊的,简化的 Treap,它的每个节点的键值预先给定,但是优先级预先给定或者随机生成

    笛卡尔树主要用于处理一个确定的数列,数列中的一个数有两个属性,在数列中的位置、数值。把位置看成键值,把数值看成优先级

    image.png

    根据这个数列构造出来的笛卡尔树符合 Treap 树的两个特征

    1. 以每个数的位置为键值,它是一颗 BST。也就是说,对这棵树左中序遍历,返回的就是数列
    2. 把数值看作 Treap 树的优先级,把数列建成一个堆。如果按大根堆建这颗树,那么在每个子树上,子树的根的权值是整棵子树上最大的

    # 用单调栈建笛卡尔树

    笛卡尔树存在 O(n)O(n)O(n) 的建树方法,考虑使用单调栈

    每次插入新的节点,横向的位置是固定的,思考新的节点的纵向位置,只需要考虑新的节点插在最右端的哪个位置,着很容易用一个单调栈来实现

    维护一个单调减的单调栈,如果新加入的节点比原来的节点小,那么按照大根堆的性质,新的节点就是栈顶节点的右儿子,如果比栈顶的节点小,就找到一个比新加入节点大的点,然后成为这个点的右儿子,新加入点的左儿子是最后一个出栈的点

    image.png

    #include <cstdio>
    #include <cstring>
    #include <string>
    #include <vector>
    #include <stack>
    #include <algorithm>
    
    using namespace std;
    const int INF = 2e9;
    const int maxn = 1e5 +7;
    struct Node{
        char s[115];
        int ls,rs,pri;
    }t[maxn];
    
    int n;
    
    void build(){
        stack<int> st; st.push(0); //t[0].pri = INF;
        for(int i=1;i<=n;i++){
            int pos=st.top();
            while(!st.empty() && t[pos].pri < t[i].pri){ // 如果栈顶元素的优先级比当前元素的优先级小,那么就一直往上找,直到找到一个优先级比当前元素大的元素
                st.pop();
                pos = st.top();
            }
            t[i].ls = t[pos].rs;
            t[pos].rs = i;
            st.push(i);
        }
    }
    
    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(")");
    }
    
    bool cmp(Node a,Node b){
        return strcmp(a.s,b.s) < 0;
    }
    
    int main(){
        freopen("1785.in","r",stdin);
        freopen("1785.out","w",stdout);
        while(scanf("%d",&n)!=EOF&&n){
            for(int i=1;i<=n;i++){
                t[i].ls=t[i].rs=0;
                scanf(" %[^/]/%d",t[i].s,&t[i].pri);
            }
            t[0].ls=t[0].rs=0; t[0].pri = INF;
            sort(t+1,t+n+1,cmp);
            build();
            inorder(t[0].rs);
            printf("\n");
        }
        return 0;
    }
    
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    上次更新: 2025/04/08, 18:03:31
    K-D Tree
    珂朵莉树

    ← K-D Tree 珂朵莉树→

    最近更新
    01
    计算机网络笔记
    06-13
    02
    LLM101 NLP学习笔记
    06-02
    03
    《python科学计算入门》学习笔记
    05-30
    更多文章>
    Theme by Vdoing | Copyright © 2024-2025 Martian148 | MIT License
    • 跟随系统
    • 浅色模式
    • 深色模式
    • 阅读模式