[JLOI2015]城池攻占

[JLOI2015]城池攻占

solution

如果战斗力最小的士兵都能存活下来，那么在堆中的其他士兵一定可以活下来
所以就从攻击力小的开始遍历一下就行。
那么我们就需要把这两个堆里面的元素合并在一起，于是我们想到用可并堆，即左偏树，记录每个士兵开始和阵亡（或活到最后）的位置，之后第二部分的答案就是开始的深度减去阵亡的深度。

code（这个码量稍大）

有点像线段树

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int N=3e5+10;
struct ltt{
	ll val,dis,laz1,laz2,s,c;
	int ls,rs,fa;
}T[N];
struct Node{
	ll f,a,v,h;
}p[N];
struct Edge{
	int to,nxt;
}e[N];
int h[N],idx;
void Ins(int a,int b){
	e[++idx].to=b;e[idx].nxt=h[a];h[a]=idx;
}
#define ls(x) T[x].ls
#define rs(x) T[x].rs
int rt[N],dep[N];
ll ans1[N],ans2[N];
inline void pushdown(int x){
	if(ls(x)){
		T[ls(x)].s=T[ls(x)].s*T[x].laz1+T[x].laz2;
		T[ls(x)].laz1*=T[x].laz1;
		T[ls(x)].laz2=T[ls(x)].laz2*T[x].laz1+T[x].laz2;
	}
	if(rs(x)){
		T[rs(x)].s=T[rs(x)].s*T[x].laz1+T[x].laz2;
		T[rs(x)].laz1*=T[x].laz1;
		T[rs(x)].laz2=T[rs(x)].laz2*T[x].laz1+T[x].laz2;
	}
	T[x].laz1=1;T[x].laz2=0;
}
int merge(int x,int y){
	if(!x||!y)return x+y;
	if(T[x].s>T[y].s)swap(x,y);
	pushdown(x),pushdown(y);
	rs(x)=merge(rs(x),y);
	if(T[ls(x)].dis<T[rs(x)].dis)
		swap(ls(x),rs(x));
	T[x].dis=T[rs(x)].dis+1;
	return x;
}
void dfs(int u,int fa){
	dep[u]=dep[fa]+1;
	for(int i=h[u];i;i=e[i].nxt){
		int v=e[i].to;
		dfs(v,u);
		rt[u]=merge(rt[u],rt[v]);
	}
	while(rt[u]&&T[rt[u]].s<p[u].h){
		pushdown(rt[u]);
		ans1[u]++;
		ans2[rt[u]]=dep[T[rt[u]].c]-dep[u];
		rt[u]=merge(ls(rt[u]),rs(rt[u]));
	}
	if(p[u].a==1){
		T[rt[u]].s*=p[u].v;
		T[rt[u]].laz1*=p[u].v;
		T[rt[u]].laz2*=p[u].v;
	}
	if(p[u].a==0){
		T[rt[u]].s+=p[u].v;
		T[rt[u]].laz2+=p[u].v;
	}
}
int main(){
	ll n,m;
	scanf("%lld%lld",&n,&m);
	for(register int i=1;i<=n;i++)
		scanf("%lld",&p[i].h);
	for(register int i=2;i<=n;i++)
		scanf("%lld%lld%lld",&p[i].f,&p[i].a,&p[i].v),Ins(p[i].f,i);
	for(register int i=1;i<=m;i++){
		scanf("%lld%lld",&T[i].s,&T[i].c);
		T[i].laz1=1;
		rt[T[i].c]=merge(rt[T[i].c],i);
	}
	dfs(1,0);
	while(rt[1]){
		pushdown(rt[1]);
		ans2[rt[1]]=dep[T[rt[1]].c];
		rt[1]=merge(ls(rt[1]),rs(rt[1]));
	}
	for(int i=1;i<=n;i++)
		printf("%lld
",ans1[i]);
	for(int i=1;i<=m;i++)
		printf("%lld
",ans2[i]);
}