Description
小铭铭最近获得了一副新的桌游，游戏中需要用 m 个骑士攻占 n 个城池。这 n 个城池用 1 到 n 的整数表示。除 1 号城池外，城池 i 会受到另一座城池 fi 的管辖，其中 fi <i。也就是说，所有城池构成了一棵有根树。这 m 个骑士用 1 到 m 的整数表示，其中第 i 个骑士的初始战斗力为 si，第一个攻击的城池为 ci。
每个城池有一个防御值 hi，如果一个骑士的战斗力大于等于城池的生命值，那么骑士就可以占领这座城池；否则占领失败，骑士将在这座城池牺牲。占领一个城池以后，骑士的战斗力将发生变化，然后继续攻击管辖这座城池的城池，直到占领 1 号城池，或牺牲为止。
除 1 号城池外，每个城池 i 会给出一个战斗力变化参数 ai;vi。若 ai =0，攻占城池 i 以后骑士战斗力会增加 vi；若 ai =1，攻占城池 i 以后，战斗力会乘以 vi。注意每个骑士是单独计算的。也就是说一个骑士攻击一座城池，不管结果如何，均不会影响其他骑士攻击这座城池的结果。
现在的问题是，对于每个城池，输出有多少个骑士在这里牺牲；对于每个骑士，输出他攻占的城池数量。
Solution
把每个骑士视为一个节点，那么对于树上每个点，要求维护其子节点的所有可并堆
可并的小根堆上同时维护乘法和加法标记
时间复杂度$O((n+m) log n)$
#include<iostream> #include<cstdio> using namespace std; int n,m,fa[300005],a[300005],head[300005],tot,c[300005],rt[300005],ch[300005][2],dis[300005],ans1[300005],ans2[300005],dep[300005]; long long h[300005],val[300005],v[300005],mlz[300005],plz[300005]; struct Edge{ int to,nxt; }edge[300005]; inline long long read(){ long long w=0,f=1; char ch=0; while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();} while(ch>='0'&&ch<='9')w=(w<<1)+(w<<3)+ch-'0',ch=getchar(); return w*f; } void cover(int x,long long k,long long b){(v[x]*=k)+=b,mlz[x]*=k,(plz[x]*=k)+=b;} void pushdown(int x){ if(ch[x][0])cover(ch[x][0],mlz[x],plz[x]); if(ch[x][1])cover(ch[x][1],mlz[x],plz[x]); mlz[x]=1,plz[x]=0; } int merge(int a,int b){ if(!a||!b)return a+b; pushdown(a),pushdown(b); if(v[a]>v[b])swap(a,b); ch[a][1]=merge(ch[a][1],b); if(dis[ch[a][0]]<dis[ch[a][1]])swap(ch[a][1],ch[a][0]); dis[a]=dis[ch[a][1]]+1; return a; } void dfs(int k,int f){ dep[k]=dep[f]+1; for(int i=head[k];i;i=edge[i].nxt)dfs(edge[i].to,k),rt[k]=merge(rt[k],rt[edge[i].to]); while(rt[k]&&v[rt[k]]<h[k])pushdown(rt[k]),ans1[k]++,ans2[rt[k]]=dep[c[rt[k]]]-dep[k],rt[k]=merge(ch[rt[k]][0],ch[rt[k]][1]); if(a[k])cover(rt[k],val[k],0); else cover(rt[k],1,val[k]); } int main(){ n=read(),m=read(); for(int i=1;i<=n;i++)h[i]=read(); for(int i=2;i<=n;i++)fa[i]=read(),a[i]=read(),val[i]=read(),edge[++tot]=(Edge){i,head[fa[i]]},head[fa[i]]=tot; for(int i=1;i<=m;i++)v[i]=read(),c[i]=read(),mlz[i]=1ll,rt[c[i]]=merge(rt[c[i]],i); dfs(1,0); while(rt[1])pushdown(rt[1]),ans2[rt[1]]=dep[c[rt[1]]],rt[1]=merge(ch[rt[1]][0],ch[rt[1]][1]); for(int i=1;i<=n;i++)printf("%d ",ans1[i]); for(int i=1;i<=m;i++)printf("%d ",ans2[i]); return 0; }