自动搬运

查看原文

来自洛谷，原作者为

	George1123 **

搬运于2025-08-24 21:47:05，当前版本为作者最后更新于2019-12-18 20:23:57，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

${\color{#00cc77}\text{欢迎拜访我这个蒟蒻的博客}}$

P3261 【[JLOI2015]城池攻占】

此题算法:左偏树-可并堆+标记下传

调了$3$天，平均每天$1$小时。

不要看我代码长，处处都是错点啊！

看到这题，就知道该这么做：

从下到上遍历树，一直拿单前节点上的骑士团中最蒻的看看会不会死在这里，再把没死的放到父亲节点上去，并改变他们的战斗力。

所以可以得出此题算法是：

luogu标签$+$最蒻$+$放到父亲节点$=$左偏树

可是骑士的能力是会变的，凡是树上批量修改需要标记下传

大致思路：

先开数组(真QwQ多)：

int fa[N],c[N],a[N],rt[N]; //树上父亲,出生地,城池能力改变方式,每个城池上骑士团左偏树的根
lng h[N],v[N],s[N]; //城池防御力,城池能力改变值,骑士能力初始值
int ls[N],rs[N],dep[N]; //堆中左子,右子,树高
int Dep[N],die[N],ans[N]; //树上深度,骑士死亡位置,城池死亡骑士数
lng add[N],tim[N]; //骑士能力变化标记(+,*)

再操作：

先将同出生城池的骑士合并为一堆。

再从$n$到$1$遍历树上城池，不停取单前城池节点小根堆顶。

如果小于城池防御力就判之死，去除堆顶。

否则跳出寻找，如果该堆已经为空，去找下一个节点。

如果堆不空，利用标记改变该堆骑士能力值。

并将骑士团合并到父亲节点骑士团。

for(int i=n;i>=1;i--){ //从下到上
	while(rt[i]!=-1){ //只要单前堆不空
		if(s[rt[i]]<h[i]){ //小于城池防御值
			die[rt[i]]=i; //判之死
			pushdown(rt[i]); //一时pushdown一时爽
			if(!ls[rt[i]]) rt[i]=-1; 
			else rt[i]=merge(ls[rt[i]],rs[rt[i]]); //去除堆顶
		} else break; //剩下的不死
	}
	if(i==1) break; //根特判
	if(rt[i]==-1) continue; //否则MLE
	if(a[i]) tim[rt[i]]*=v[i],add[rt[i]]*=v[i],s[rt[i]]*=v[i];
	else add[rt[i]]+=v[i],s[rt[i]]+=v[i];
	//利用标记，修改该堆骑士能力值
	pushdown(rt[i]); //一直pushdown一直爽
	if(rt[fa[i]]==-1) rt[fa[i]]=rt[i];
	else rt[fa[i]]=merge(rt[fa[i]],rt[i]); //父亲城池等待着幸存的骑士
}

$pushdown()$：根据单前标记，先改左右子树能力值，再改左右子树标记值，最后清空单前节点标记。

合并堆$merge()$：这是左偏树的全部精华，不会去模板题学。

清空标记：加标记为$0$，乘标记为$1$。

这之后，再令每个$ans[die[i]]++$，就只剩输出了。

先输出$n$个$ans[i]$，再输出$m$个$Dep[c[i]]-Dep[die[i]]$。

以下是代码+注释

#include <bits/stdc++.h>
using namespace std;
#define lng long long
const int N=3e5+10; //It's turly fat
int n,m;
int fa[N],c[N],a[N],rt[N]; //树上父亲,出生地,城池能力改变方式,每个城池上骑士团左偏树的根
lng h[N],v[N],s[N]; //城池防御力,城池能力改变值,骑士能力初始值
int ls[N],rs[N],dep[N]; //堆中左子,右子,树高
int Dep[N],die[N],ans[N]; //树上深度,骑士死亡位置,城池死亡骑士数
lng add[N],tim[N]; //骑士能力变化标记(+,*)
void pushdown(int x){ //标记下传
	if(add[x]==0&&tim[x]==1)
		return;
	if(ls[x]){
		tim[ls[x]]*=tim[x];
		add[ls[x]]*=tim[x];
		add[ls[x]]+=add[x];
		s[ls[x]]*=tim[x];
		s[ls[x]]+=add[x];
	} 
	if(rs[x]){
		tim[rs[x]]*=tim[x];
		add[rs[x]]*=tim[x];
		add[rs[x]]+=add[x];
		s[rs[x]]*=tim[x];
		s[rs[x]]+=add[x];
	}
	add[x]=0,tim[x]=1;
}
int merge(int x,int y){ //合并堆
	if(!x||!y) return x^y;
	pushdown(x),pushdown(y);
	if(s[x]>s[y]) swap(x,y);
	rs[x]=merge(rs[x],y);
	if(dep[ls[x]]<dep[rs[x]])
		swap(ls[x],rs[x]);
	dep[x]=dep[ls[x]]+1;
	return x;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%lld",h+i);
		rt[i]=-1; //设为空
	}
	Dep[1]=1,dep[0]=-1;
	for(int i=2;i<=n;i++){
		scanf("%d%d%lld",fa+i,a+i,v+i);
		Dep[i]=Dep[fa[i]]+1; //不用dfs求Dep
	}
	for(int i=1;i<=m;i++){
		scanf("%lld%d",s+i,c+i);
		tim[i]=1; //It's very important!
		if(rt[c[i]]==-1) rt[c[i]]=i;
		else rt[c[i]]=merge(rt[c[i]],i); //合并同城骑士
	}
	for(int i=n;i>=1;i--){ //从下到上
		while(rt[i]!=-1){ //只要单前堆不空
			if(s[rt[i]]<h[i]){ //小于城池防御值
				die[rt[i]]=i; //判之死
				pushdown(rt[i]); //一时pushdown一时爽
				if(!ls[rt[i]]) rt[i]=-1;
				else rt[i]=merge(ls[rt[i]],rs[rt[i]]);
			} else break; //剩下的不死
		}
		if(i==1) break; //根特判
		if(rt[i]==-1) continue; //否则MLE
		if(a[i]) tim[rt[i]]*=v[i],add[rt[i]]*=v[i],s[rt[i]]*=v[i];
		else add[rt[i]]+=v[i],s[rt[i]]+=v[i];
		//利用标记，修改该堆骑士能力值
		pushdown(rt[i]); //一直pushdown一直爽
		if(rt[fa[i]]==-1) rt[fa[i]]=rt[i];
		else rt[fa[i]]=merge(rt[fa[i]],rt[i]); //父亲城池等待着幸存的骑士
	}
	for(int i=1;i<=m;i++)
		ans[die[i]]++; 
	for(int i=1;i<=n;i++)
		printf("%d\n",ans[i]); //输出，结束
	for(int i=1;i<=m;i++)
		printf("%d\n",Dep[c[i]]-Dep[die[i]]);
	return 0;
}

几个恐怖的错误：

top 4 $tim[]$数组在$1-n$的循环中初始化。

top 3 不初始化$dep[0]=-1$。

top 2 不在加标记的同时改$s[]$数组。

top 1 不特判骑士死光的情况(莫名MLE极其恐怖)。

写题解不易，快点个赞吧。

谢谢大家 ! !