左偏树的基础操作和例题：左偏树——可以标记合并的堆
左偏树是可并堆中好写也优秀的一种
顾名思义就是可以合并的堆。
经常见于树上问题
只关心子树的最大值的时候，可以用可并堆
（PS：线段树合并也可以代替之，但是空间大；平衡树启发式合并也可以代替之，但是常数太大）
打标记：
干掉骑士弹出的时候，别忘了判断堆是否为空！
#include<bits/stdc++.h> #define reg register int #define il inline #define numb (ch^'0') using namespace std; typedef long long ll; il void rd(int &x){ char ch;x=0;bool fl=false; while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true); for(x=numb;isdigit(ch=getchar());x=x*10+numb); (fl==true)&&(x=-x); } namespace Miracle{ const int N=300000+5; int n,m; struct node{ int nxt,to; }e[2*N]; int hd[N],cnt; void add(int x,int y){ e[++cnt].nxt=hd[x]; e[cnt].to=y; hd[x]=cnt; } struct tr{ ll val; ll add; ll mul; //int sz; int ls,rs; int d; int id; tr(){} tr(ll v,int iidd){ val=v;mul=1;add=0; d=1;ls=0;rs=0; id=iidd; } }t[N]; int tot; //void pushup(int x){ // t[x].sz=t[t[x].ls].sz+t[t[x].rs].sz+1; //} void pushdown(int x){ t[t[x].ls].val=(t[t[x].ls].val*t[x].mul+t[x].add); t[t[x].ls].add=(t[t[x].ls].add*t[x].mul+t[x].add); t[t[x].ls].mul*=t[x].mul; t[t[x].rs].val=(t[t[x].rs].val*t[x].mul+t[x].add); t[t[x].rs].add=(t[t[x].rs].add*t[x].mul+t[x].add); t[t[x].rs].mul*=t[x].mul; t[x].add=0; t[x].mul=1; } int merge(int x,int y){ if(!x||!y) return x+y; pushdown(x);pushdown(y); if(t[x].val>t[y].val) swap(x,y); t[x].rs=merge(t[x].rs,y); if(t[t[x].ls].d<t[t[x].rs].d) swap(t[x].ls,t[x].rs); t[x].d=t[t[x].rs].d+1; // pushup(x); return x; } void mul(int x,ll c){ if(!x) return; t[x].mul*=c; t[x].add*=c; t[x].val*=c; } void add(int x,ll c){ if(!x) return; t[x].add+=c; t[x].val+=c; } int dele(int x){ pushdown(x); return merge(t[x].ls,t[x].rs); } ll a[N],v[N],h[N]; ll s[N]; int st[N]; vector<int>mem[N]; int dep[N]; int got[N];//knight int ans[N];//city int rt[N]; void dfs(int x,int d){ //cout<<" x "<<x<<" dep "<<d<<endl; dep[x]=d; for(reg i=hd[x];i;i=e[i].nxt){ int y=e[i].to; dfs(y,d+1); rt[x]=merge(rt[x],rt[y]); } //cout<<" back to "<<x<<" dep "<<d<<endl; for(reg i=0;i<(int)mem[x].size();++i){ t[++tot]=tr(s[mem[x][i]],mem[x][i]); rt[x]=merge(rt[x],tot); } //cout<<" add new "<<tot<<endl; while(rt[x]&&t[rt[x]].val<h[x]){ ++ans[x]; int id=t[rt[x]].id; got[id]=dep[st[id]]-dep[x]; rt[x]=dele(rt[x]); } //cout<<" had gone "<<ans[x]<<endl; if(x!=1){ if(a[x]==0) add(rt[x],v[x]); else mul(rt[x],v[x]); } else{ while(rt[x]){ int id=t[rt[x]].id; got[id]=dep[st[id]]; rt[x]=dele(rt[x]); } } //cout<<" after tag and return "<<x<<endl; } int main(){ rd(n);rd(m); for(reg i=1;i<=n;++i) scanf("%lld",&h[i]); int fa; for(reg i=2;i<=n;++i){ rd(fa);scanf("%lld%lld",&a[i],&v[i]); add(fa,i); } for(reg i=1;i<=m;++i){ scanf("%lld%d",&s[i],&st[i]); mem[st[i]].push_back(i); } //cout<<" after pre "<<endl; dfs(1,1); for(reg i=1;i<=n;++i){ printf("%d ",ans[i]); } for(reg i=1;i<=m;++i){ printf("%d ",got[i]); } return 0; } } signed main(){ // freopen("5.in","r",stdin); // freopen("my.out","w",stdout); Miracle::main(); return 0; } /* Author: *Miracle* Date: 2019/2/12 19:24:36 */
优化DP：
给出m条有权的树链，覆盖整个树的最小代价
n,m<=1e5
考虑树形dp
子树合并，直接开数组是O(n^2)的
其实总共的链只有m条
就用数据结构当数组来使。
f[i]是一个集合{(d,c)}
d:深度为d 合并的时候两种可能：
1.子树能覆盖上去 子树每个点打标记：(d,c)->(d,c+min(A)+min(C)+min(D)....) B的这个d要覆盖i才行，， 所以懒惰删除 如果A，C,D...的堆顶不能覆盖自己的话，那么pop掉
B先不用管，不合法的用到的时候会pop掉的
2.自己开一个链 add (d,cosnow+min(A)+min(B)....)
可持久化：
求树上路径前k小
考虑，一个全局堆，开始把每个位置贡献的最小值放进去，取出来一个，把有关这个点的次小值放进去。
只要能快速支持每个位置求下一个值即可。
“位置”：这里每个点i，维护以i为开头的所有链的信息。
考虑树形dp的思路：
两个堆：
f[i]：i往子树内 g[i]：i往子树外
对于f[i]的合并：每个儿子整体加上边权再合并上来；
对于g[i]的合并，再扫一遍，g[i]=merge(g[fa[i]],fpre[i],fbac[i])+w（整体加上边权w），fpre[i]是i关于fa[i]的前缀兄弟，fbac同理
（这里很像换根）
由于要不断查询，所以所有的堆必须可持久化
可持久化应该类似fhq的可持久化？还要标记永久化
（标记永久化的合并。。。。。。咕咕咕）
（或者你暴力新建节点，，，空间复杂度+常数未知。。。）