模板汇总——左偏树

迈不过友情╰ 2021-12-15 14:51 226阅读 0赞

已封装：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

class Left_Heap{
    public:
        static const int Mn = N;
        int ls[Mn], rs[Mn], rt[Mn], val[Mn], pos[Mn], dis[Mn];
        int n;
        void init(){
            for(int i = 1; i <= n; ++i){
                ls[i] = rs[i] = dis[i] = 0;
                rt[i] = pos[i] = i;
            }
            dis[0] = -1;
        }
        bool cmp(int t1, int t2){
            if(val[t1] == val[t2]) return pos[t1] < pos[t2];
            return val[t1] < val[t2];
        }
        int Find(int x){
            if(x == rt[x]) return x;
            return rt[x] = Find(rt[x]);
        }
        int Merge(int u, int v){
            if(u == v) return u;
            if(!u || !v) return u+v;
            if(!cmp(u, v)) swap(u, v);
            rs[u] = Merge(rs[u], v);
            rt[rs[u]] = u;
            if(dis[ls[u]] < dis[rs[u]]) swap(ls[u], rs[u]);
            dis[u] = dis[rs[u]] + 1;
            return u;
        }
        int Pop(int u){
            if(!u || pos[u] == -1) return -1;
            u = Find(u);
            rt[ls[u]] = ls[u];
            rt[rs[u]] = rs[u];
            rt[u] = Merge(ls[u], rs[u]);
            pos[u] = -1;
            return val[u];
        }
        void Unit(int u, int v){
            if(pos[u] == -1 || pos[v] == -1) return ;
            u = Find(u); v = Find(v);
            if(u == v) return ;
            Merge(u, v);
            return ;
        }
    }tr;

转载于:https://www.cnblogs.com/MingSD/p/10457718.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211214/2bfe3842d46446eda4f443e47af2b576.png

发表评论取消回复

表情：

评论列表（有 0 条评论，226人围观）

还没有评论，来说两句吧...

相关阅读

相关左偏树

题目描述如题，一开始有N个小根堆，每个堆包含且仅包含一个数。接下来需要支持两种操作：操作1： 1 x y 将第x个数和第y个数所在的小根堆合并（若第x或第y个数...

朴灿烈づ我的快乐病毒、/ 2024年04月18日 19:51/ 0 赞/ 61 阅读

相关【左偏树】 [JLOI2015]城池攻占

原来左偏树还可以打tag，get了和线段树打tag一样，时不时Push\_Down就好了然后这里显然也是要先乘法后加法的 tag打上了之后还是其他一般左偏树差不多，有

刺骨的言语ヽ痛彻心扉/ 2023年06月01日 06:08/ 0 赞/ 27 阅读

相关【左偏树】[APIO2012]派遣

题意可真的是有毒第一眼树形背包可做？（反正我没用树形背包打过，边上巨佬打的背包似乎没拿分）后来发现可以贪心搞，我们先把一个节点所有的儿子都取进去，之后不行的话再从大的开

刺骨的言语ヽ痛彻心扉/ 2023年06月01日 06:08/ 0 赞/ 10 阅读

相关【左偏树】[LuoguP1456] Monkey King

多...多组数据... awsl 死命的MLE，原来是忘记清空数组了.... 左偏树模板？对于每一个操作，我们把两个节点$x,y$的祖先$fx,fy$找到，然后把他们

客官°小女子只卖身不卖艺/ 2023年06月01日 06:08/ 0 赞/ 17 阅读

相关模板的偏特化

template <class Window, class Controller> class Widget { ....

Dear 丶/ 2022年08月13日 19:39/ 0 赞/ 216 阅读

相关 HDU 1512 Monkey King（左偏树）

题目链接： [HDU 1512][] 题意：有 n 只猴子，每只猴子都有一个力量，开始时互相都不认识，它们之间发生 m 次争斗，每次发生a,b发生争斗时，a,b会从

蔚落/ 2022年06月08日 09:51/ 0 赞/ 162 阅读

相关左偏树模板（以洛谷P3377 为例）

题目：[点击打开链接][Link 1] 题意：略。分析：左偏树（可并堆）模板题，配对堆或者斐波那契堆也可以做。左偏树入门参考[https://www.luogu.o

Bertha 。/ 2022年04月14日 02:19/ 0 赞/ 329 阅读

相关模板汇总——左偏树

已封装： ![ContractedBlock.gif][] ![ExpandedBlockStart.gif][] class Left_Heap{ pub

迈不过友情╰/ 2021年12月15日 14:51/ 0 赞/ 227 阅读

相关模板汇总——笛卡尔树

笛卡尔树 O(n)建立一颗该节点是当前子树的最值的二叉树. 代码: ![ContractedBlock.gif][] ![ExpandedBlockStart.gi

た入场券/ 2021年10月19日 04:24/ 0 赞/ 326 阅读

相关 BZOJ 2333 左偏树（写得我人生都崩溃了...）

思路：高一神犇竟然问我这道题我光荣地看着题解（划掉）写了一下午 QaQ multiset不能erase(一个值) 这样就把等于这个值的数都eras

浅浅的花香味﹌/ 2021年10月01日 03:26/ 0 赞/ 245 阅读