menu ZigZagK的博客
account_circle

正在努力加载中QAQ

[可并堆]BZOJ4003(JLOI2015)【城池攻占】题解
apps BZOJ
local_offer 查看标签
comment 0 条评论

题目概述

有一棵 $n$ 个节点的树,每个节点有个防御值。有 $m$ 个骑士在树的节点上,如果骑士攻击力大于等于防御值就可以攻占这个节点获得收益并向上攻占,否则凉凉。问每个节点凉了多少骑士,每个骑士在凉之前占了多少节点。

解题报告

听说倍增过不了……不过可并堆也很斯波啊。从下往上合并节点,每次挑出攻击力最小的骑士,如果不能攻占就凉凉,否则打tag。好像DFS会爆栈?拓扑一下就行了。我已经不会左偏树了,随机堆真好用。

示例程序

#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=300000,maxm=300000;

int n,m,tp[maxn+5],cnt[maxn+5],dis[maxm+5];LL h[maxn+5],v[maxn+5];
int E,lnk[maxn+5],son[maxn+5],nxt[maxn+5],d[maxn+5],Head,Tail,que[maxn+5];
int RD[1000000],si,ro[maxn+5],ls[maxm+5],rs[maxm+5];LL w[maxm+5],add[maxm+5],mul[maxm+5];int tag[maxm+5];

inline int Rand() {static int pos=0;return RD[pos<1e6?pos++:pos=0];}
inline void Make() {srand(759405);for (int i=0;i<1e6;i++) RD[i]=rand()&1;}
#define Add(x,y) (son[++E]=(y),nxt[E]=lnk[x],lnk[x]=E)
inline void Addmul(int x,LL k) {if (!x) return;w[x]*=k;add[x]*=k;mul[x]*=k;}
inline void Addadd(int x,LL k) {if (!x) return;w[x]+=k;add[x]+=k;}
inline void Addtag(int x,int k) {if (!x) return;dis[x]+=k;tag[x]+=k;}
inline void Pushdown(int p){
    if (mul[p]>1) Addmul(ls[p],mul[p]),Addmul(rs[p],mul[p]),mul[p]=1;
    if (add[p]) Addadd(ls[p],add[p]),Addadd(rs[p],add[p]),add[p]=0;
    if (tag[p]) Addtag(ls[p],tag[p]),Addtag(rs[p],tag[p]),tag[p]=0;
}
int Merge(int A,int B){
    if (!A||!B) return A+B;if (w[A]>w[B]) swap(A,B);int d=Rand();
    Pushdown(A);d?ls[A]=Merge(ls[A],B):rs[A]=Merge(rs[A],B);return A;
}
void Travel(int x) {if (!x) return;Pushdown(x);Travel(ls[x]);Travel(rs[x]);}
inline void Count(int x){
    while (ro[x]&&w[ro[x]]<h[x]) Pushdown(ro[x]),ro[x]=Merge(ls[ro[x]],rs[ro[x]]),cnt[x]++;
    tp[x]?Addmul(ro[x],v[x]):Addadd(ro[x],v[x]);Addtag(ro[x],1);
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    Make();scanf("%d%d",&n,&m);for (int i=1;i<=n;i++) scanf("%lld",&h[i]);
    for (int i=2,fa;i<=n;i++) scanf("%d%d%lld",&fa,&tp[i],&v[i]),Add(i,fa),d[fa]++;
    for (int i=1;i<=m;i++) {LL x;int y;scanf("%lld%d",&x,&y);w[++si]=x;mul[si]=1;ro[y]=Merge(ro[y],si);}
    for (int i=1;i<=n;i++) if (!d[i]) que[++Tail]=i,Count(i);
    while (Head!=Tail)
        for (int x=que[++Head],j=lnk[x];j;j=nxt[j])
            {int u=son[j];ro[u]=Merge(ro[u],ro[x]);d[u]--;if (!d[u]) Count(u),que[++Tail]=u;}Travel(ro[1]);
    for (int i=1;i<=n;i++) printf("%d\n",cnt[i]);for (int i=1;i<=m;i++) printf("%d\n",dis[i]);return 0;
}
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!
名称不能为空
email
邮箱不能为空,请填写正确格式
link
网址请用http://或https://开头
message
评论不能为空
资瓷Markdown和LaTex数学公式
sentiment_very_satisfied
keyboard_arrow_up