用左偏树不断向上维护仍在[浴血奋战的]骑士攻击力，不断维护tag维护即可
#include<cstdio> #include<cctype> #define ml(x) tr[x].ml #define ad(x) tr[x].ad #define ls(x) tr[x].l #define rs(x) tr[x].r #define vl(x) tr[x].val inline char nc(){ static char buf[100000],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++; } #define M 500000 typedef long long ll; const int N=3e5+5; template<class T>inline void read(T &x){ char ch=nc();x=0;ll f=1; for(;!isdigit(ch);ch=nc())if(ch=='-')f=-1; for(;isdigit(ch);ch=nc())x=(x<<1)+(x<<3)+ch-'0'; x*=f; } int a[N]; int n,m,cnt,c[N],rt[N],dep[N],head[N],nex[N],to[N],s[N],ans[N]; ll h[N],v[N]; struct data{int dis,l,r;ll ml,ad,val;}tr[N]; inline void swap(int &x,int &y){int tmp=x;x=y,y=tmp;} inline void addedge(int u,int v){ nex[++cnt]=head[u],head[u]=cnt,to[cnt]=v; } inline void pushdown(int x){ if(ls(x))vl(ls(x))=vl(ls(x))*ml(x)+ad(x),ml(ls(x))*=ml(x),ad(ls(x))=ad(ls(x))*ml(x)+ad(x); if(rs(x))vl(rs(x))=vl(rs(x))*ml(x)+ad(x),ml(rs(x))*=ml(x),ad(rs(x))=ad(rs(x))*ml(x)+ad(x); ml(x)=1,ad(x)=0; } inline int merge(int x,int y){ if(!x||!y)return x+y; pushdown(x),pushdown(y); if(vl(x)>vl(y))swap(x,y); rs(x)=merge(rs(x),y); if(tr[ls(x)].dis<tr[rs(x)].dis)swap(ls(x),rs(x)); tr[x].dis=tr[ls(x)].dis+1; return x; } inline void dfs(int x){ for(int t,i=head[x];i;i=nex[i]){ t=to[i],dep[t]=dep[x]+1,dfs(t); if(!a[t])vl(rt[t])+=v[t],ad(rt[t])+=v[t]; else vl(rt[t])*=v[t],ad(rt[t])*=v[t],ml(rt[t])*=v[t]; rt[x]=merge(rt[x],rt[t]); } while(rt[x]&&vl(rt[x])<h[x])ans[rt[x]]=x,pushdown(rt[x]),s[x]++,rt[x]=merge(ls(rt[x]),rs(rt[x])); } inline void write(int x){ if(x<10)putchar(x+'0'); else write(x/10),putchar((x)+'0'); } int main(){ read(n),read(m),dep[0]=-1;; for(int i=1;i<=n;i++)read(h[i]); for(int x,i=2;i<=n;i++)read(x),addedge(x,i),read(a[i]),read(v[i]); for(int i=1;i<=m;i++){ read(tr[i].val),read(c[i]),tr[i].ml=1; rt[c[i]]=merge(rt[c[i]],i); } dfs(1); for(int i=1;i<=n;i++)write(s[i]),puts(""); for(int i=1;i<=m;i++)write(dep[c[i]]-dep[ans[i]]),puts(""); return 0; }转载于:https://www.cnblogs.com/MikuKnight/p/9863073.html
相关资源：JAVA上百实例源码以及开源项目