可持久化左偏树

闲来无事想学k短路，但看着很难打（ 顺手学的可持久化左偏树倒是容易，来写一发 基本思路就是每次merge的时候将普通左偏树里准备作为新的根的结点copy一个，对新结点搞事 然后所有操作基于merge 然后就没了（ 最近比较懒不想写泛型和OOP，OIer码风将就一下（ 什么时候写好了泛型单独放代码 ```cpp struct Node { int val; Node *lc,*rc; int npl; Node(int v): val(v), lc(NULL), rc(NULL), npl(1) {} }; Node *root[1<<10]; int vertot; Node *merge(Node *l,Node *r) { if(l==NULL)return r; if(r==NULL)return l; if(l->val>r->val)std::swap(l,r); Node *ptr=new Node(*l);//全文与普通左偏树唯一的不同之处 ptr->rc=merge(ptr->rc,r); if(ptr->lc==NULL||ptr->lc->npl<ptr->rc->npl) { std::swap(ptr->lc,ptr->rc); } ptr->npl=ptr->rc!=NULL?ptr->rc->npl+1:1; return ptr; } Node *push(int val,Node *rt) { return merge(new Node(val),rt); } int top(Node *rt) { return rt->val; } Node *pop(Node *rt) { return merge(rt->lc,rt->rc); } ```