[BZOJ4003/Luogu3261][JLOI2015]城池攻占(可并堆,左偏树)

发布于 2018-02-16  93 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ4003/Luogu3261][JLOI2015]城池攻占(可并堆,左偏树)

Description

小铭铭最近获得了一副新的桌游,游戏中需要用 m 个骑士攻占 n 个城池。
这 n 个城池用 1 到 n 的整数表示。除 1 号城池外,城池 i 会受到另一座城池 fi 的管辖,其中 fi i。也就是说,所有城池构成了一棵有根树。这 m 个骑士用 1 到 m 的整数表示,其中第 i 个骑士的初始战斗力为 si,第一个攻击的城池为 ci。每个城池有一个防御值 hi,如果一个骑士的战斗力大于等于城池的生命值,那么骑士就可以占领这座城池;否则占领失败,骑士将在这座城池牺牲。占领一个城池以后,骑士的战斗力将发生变化,然后继续攻击管辖这座城池的城池,直到占领 1 号城池,或牺牲为止。除 1 号城池外,每个城池 i 会给出一个战斗力变化参数 ai;vi。若 ai =0,攻占城池 i 以后骑士战斗力会增加 vi;若 ai =1,攻占城池 i 以后,战斗力会乘以 vi。注意每个骑士是单独计算的。也就是说一个骑士攻击一座城池,不管结果如何,均不会影响其他骑士攻击这座城池的结果。现在的问题是,对于每个城池,输出有多少个骑士在这里牺牲;对于每个骑士,输出他攻占的城池数量。

Http

BZOJ
Luogu

Tag

可并堆,左偏树

解决思路

考虑到每一个骑士是单独算的,那么我们可以用堆来维护到达每一个点的骑士的攻击值,弹出那些不能攻占的,剩下的打上乘或加的标记。
那么考虑到有把堆合并的操作,这里采用左偏树实现可并堆。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=300100;
const int inf=2147483647;

class Heap//左偏树
{
public:
    ll key,plus,mul;//plus加标记,mul乘标记
    int ch[2],dis;
    Heap()
        {
            plus=0;mul=1;
            return;
        }
};

int n,m;
int edgecnt=-1,Head[maxN],Next[maxN*2],V[maxN*2];
int Id[maxN];//这里用Id表示树上某个点对应的堆的根节点
ll Def[maxN],Opt[maxN],Val[maxN],Depth[maxN];
int St[maxN],Ed[maxN],Fail[maxN];//St记录每一个骑士出发的点,Ed记录每一个骑士牺牲的点,两点深度之差就是骑士攻占的城市个数,Fail记录在某城市牺牲的骑士个数
Heap H[maxN];

int Merge(int r1,int r2);
void PushDown(int rt);//标记下放
void Mark(int rt,ll plus,ll mul);//标记
void dfs(int u);//dfs从下到上合并

int main()
{
    mem(Head,-1);
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++) scanf("%lld",&Def[i]);
    for (int i=2;i<=n;i++)
    {
        int fa;scanf("%d%lld%lld",&fa,&Opt[i],&Val[i]);
        edgecnt++;Next[edgecnt]=Head[fa];Head[fa]=edgecnt;V[edgecnt]=i;
    }
    for (int i=1;i<=m;i++)
    {
        scanf("%lld%d",&H[i].key,&St[i]);
        if (Id[St[i]]==0) Id[St[i]]=i;
        else Id[St[i]]=Merge(Id[St[i]],i);
    }
    Depth[1]=1;dfs(1);
    for (int i=1;i<=n;i++) printf("%d\n",Fail[i]);
    for (int i=1;i<=m;i++) printf("%lld\n",Depth[St[i]]-Depth[Ed[i]]);
    return 0;
}

int Merge(int r1,int r2)//左偏树合并核心操作
{
    if (r1==0) return r2;
    if (r2==0) return r1;
    PushDown(r1);PushDown(r2);
    if (H[r1].key>H[r2].key) swap(r1,r2);
    H[r1].ch[1]=Merge(H[r1].ch[1],r2);
    if (H[H[r1].ch[0]].dis<H[H[r1].ch[1]].dis) swap(H[r1].ch[0],H[r1].ch[1]);
    if (H[r1].ch[1]) H[r1].dis=H[H[r1].ch[1]].dis+1;
    else H[r1].dis=0;
    return r1;
}

void PushDown(int rt)
{
    if (H[rt].ch[0]) Mark(H[rt].ch[0],H[rt].plus,H[rt].mul);
    if (H[rt].ch[1]) Mark(H[rt].ch[1],H[rt].plus,H[rt].mul);
    H[rt].mul=1;H[rt].plus=0;return;
}

void Mark(int rt,ll plus,ll mul)
{
    H[rt].key=H[rt].key*mul+plus;
    H[rt].plus=H[rt].plus*mul+plus;
    H[rt].mul=H[rt].mul*mul;
    return;
}

void dfs(int u)
{
    for (int i=Head[u];i!=-1;i=Next[i])
        Depth[V[i]]=Depth[u]+1,dfs(V[i]);
    for (int i=Head[u];i!=-1;i=Next[i])
    {
        if (Id[V[i]]==0) continue;
        if (Id[u]==0) Id[u]=Id[V[i]];
        else Id[u]=Merge(Id[u],Id[V[i]]);
    }
    while ((Id[u])&&(H[Id[u]].key<Def[u]))
    {
        Fail[u]++;Ed[Id[u]]=u;
        PushDown(Id[u]);Id[u]=Merge(H[Id[u]].ch[0],H[Id[u]].ch[1]);
    }
    if (Id[u])
    {
        if (Opt[u]==0) Mark(Id[u],Val[u],1);
        if (Opt[u]==1) Mark(Id[u],0,Val[u]);
    }
    return;
}

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ4003/Luogu3261][JLOI2015]城池攻占(可并堆,左偏树)


HNCJ OIer