[bzoj4003][JLOI2015]城池攻占_左偏樹

城池攻占?bzoj-4003 JLOI-2015

　　　　題目大意：一顆n個節點的有根數，m個有初始戰斗力的騎士都站在節點上。每一個節點有一個standard，如果這個騎士的戰斗力超過了這個門檻，他就會根據城池的獎勵增加自己的戰斗力。具體地：每一個城池有一個flag和一個val，表示成功到達這個城市的騎士的戰斗力會乘上val還是加上val。每個騎士都只會向根節點進攻。輸出每個騎士敗北的城市編號。如果這個騎士成功到達根節點，輸出0。

　　　　注釋：$1\le n,m \le 3\cdot 10^5$，$-10^{18}\le standard , val , attack \le 10^{18}$。保證每一個騎士的atk不大于longlong。

　　　　　　想法：GXZlegend可并堆例題。和上兩道題類似地，我們對于每一個城池維護一個小根堆，元素是是當前節點為子樹里的騎士到達這里的atk，我們自底向頂修改城墻，順便將騎士向上推，以及標記的下傳。我們在merge函數中完成pushdown的操作。特別地，在維護雙標記的時候我默認是先乘后加，所以在pushdown的時候如果發現有乘法標記的話需要先將加法標記擴大，再下傳。

　　　　最后，附上丑陋的代碼... ...

#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 300010
using namespace std;
typedef long long ll;
int head[N],to[N],type[N],next[N],cnt,root[N],l[N],r[N],d[N],deep[N],from[N],kill[N],atk[N];
ll val[N],h[N],key[N],tadd[N],tmul[N];
inline void add(int x,int y,int a,ll b)
{to[++cnt]=y;type[cnt]=a;val[cnt]=b;next[cnt]=head[x];head[x]=cnt;
}
inline void pushdown(int x)
{if(!x)return;if(tmul[x]!=1){key[l[x]]*=tmul[x];tadd[l[x]]*=tmul[x];tmul[l[x]]*=tmul[x];key[r[x]]*=tmul[x];tadd[r[x]]*=tmul[x];tmul[r[x]]*=tmul[x];tmul[x]=1;}if(tadd[x]){key[l[x]]+=tadd[x];tadd[l[x]]+=tadd[x];key[r[x]]+=tadd[x];tadd[r[x]]+=tadd[x];tadd[x]=0;}
}
int merge(int x,int y)
{if(!x) return y;if(!y) return x;pushdown(x),pushdown(y);if(key[x]>key[y]) swap(x,y);r[x]=merge(r[x],y);if(d[l[x]]<d[r[x]]) swap(l[x],r[x]);d[x]=d[r[x]]+1;return x;
}
void dfs(int x)
{for(int i=head[x];i;i=next[i]){deep[to[i]]=deep[x]+1;dfs(to[i]);if(type[i]){key[root[to[i]]]*=val[i];tadd[root[to[i]]]*=val[i];tmul[root[to[i]]]*=val[i];}else{key[root[to[i]]]+=val[i];tadd[root[to[i]]]+=val[i];}root[x]=merge(root[x],root[to[i]]);}while(root[x]&&key[root[x]]<h[x]){kill[x]++,atk[root[x]]=x,pushdown(root[x]),root[x]=merge(l[root[x]],r[root[x]]);}
}
int main()
{int n,m,x,a;ll b;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) scanf("%lld",&h[i]);for(int i=2;i<=n;i++) scanf("%d%d%lld",&x,&a,&b),add(x,i,a,b);for(int i=1;i<=m;i++){tmul[i]=1,scanf("%lld%d",&key[i],&from[i]),root[from[i]]=merge(root[from[i]],i);}d[0]=-1,deep[1]=1;dfs(1);for(int i=1;i<=n;i++){printf("%d\n",kill[i]);}for(int i=1;i<=m;i++){printf("%d\n",deep[from[i]]-deep[atk[i]]);}return 0;
}

?

　　　　小結：type標記存在哪里都無所謂qwq

?