正題

題目鏈接:https://www.luogu.com.cn/problem/P3261

---

題目大意

$n$個點的樹，每個節點有一個防御值和一個攻擊后的影響(讓你的傷害加上一個數或者乘上一個數)

然后$m$個騎士，給定初始攻擊點和初始傷害，不停往上走，遇到防御小于他傷害的城堡就攻占否則就死亡

求每個城堡干死了多少個勇士，每個勇士干死了多少個城堡。

---

解題思路

顯然以傷害建立一個小根堆，每次想不滿足的丟出去，然后打上延遲標記全部修改。然后每次把所有子樹的堆都合并。

這里比較懶就騎士和節點都建立了堆，所有速度比較慢。

---

$code$

#pragma GCC optimize(2) %:pragma GCC optimize(3) %:pragma GCC optimize("Ofast") %:pragma GCC optimize("inline") #include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=6e5+10; ll n,m,h[N],dep[N],ans1[N],ans2[N],val[N]; struct Left_Tree{#define ls t[x][0]#define rs t[x][1]ll fa[N],add[N],mul[N],dis[N],t[N][2];void Change(ll x,ll v1,ll v2){if(!x) return;val[x]*=v1;val[x]+=v2;add[x]*=v1;mul[x]*=v1;add[x]+=v2;return;}void PushDown(ll x){Change(ls,mul[x],add[x]);Change(rs,mul[x],add[x]);mul[x]=1;add[x]=0;return;}ll Get(ll x){return (fa[x]==x)?(x):(fa[x]=Get(fa[x]));}ll Merge(ll x,ll y){if(!x||!y) return x+y;if(val[x]>val[y]) swap(x,y);PushDown(x);PushDown(y);rs=Merge(rs,y);fa[ls]=fa[rs]=x;if(dis[ls]<dis[rs]) swap(ls,rs);dis[x]=dis[rs]+1;return x;}void Del(ll x){PushDown(x);Change(x,0,0);fa[ls]=ls;fa[rs]=rs;fa[x]=Merge(ls,rs);return;} #undef ls#undef rs }T; struct node{ll to,next; }a[N]; ll mul[N],add[N],s[N],ls[N],tot; void addl(ll x,ll y){a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;return; } void dfs(ll x){for(ll i=ls[x];i;i=a[i].next){ll y=a[i].to;dep[y]=dep[x]+1;dfs(y);T.Merge(T.Get(x),T.Get(y));}ll k;while(val[k=T.Get(x)]<h[x]&&k){if(k>n){ans1[x]++;ans2[k-n]=dep[s[k-n]]-dep[x];}T.Del(k);}T.Change(T.Get(x),mul[x],add[x]);return; } int main() {scanf("%lld%lld",&n,&m);for(ll i=1;i<=n;i++)scanf("%lld",&h[i]),T.fa[i]=i,mul[i]=1;for(ll i=2;i<=n;i++){ll op,x,y;scanf("%lld%lld%lld",&x,&op,&y);if(op) mul[i]=y;else add[i]=y;addl(x,i);}for(ll i=1;i<=m;i++){scanf("%lld%lld",&val[i+n],&s[i]);ans2[i]=-1;T.fa[i+n]=i+n;T.Merge(i+n,T.Get(s[i]));}dep[1]=1;dfs(1);for(ll i=1;i<=n;i++)printf("%lld\n",ans1[i]);for(ll i=1;i<=m;i++)if(ans2[i]<0) printf("%lld\n",dep[s[i]]);else printf("%lld\n",ans2[i]);return 0; }

總結

以上是生活随笔為你收集整理的P3261-[JLOI2015]城池攻占【左偏树】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。