题解 P3261 【[JLOI2015]城池攻占】

· · 题解

{\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极其恐怖)。

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

谢谢大家 ! !