题目链接

洛谷

darkbzoj

题意简述

给你一棵树，每个节点有 $h$ 值，一个勇士来到一个节点时如果他的战斗力大于等于 $h$ 就能占领城池并前往这个节点的父亲（除非已经到了根节点），否则阵亡；攻占一个节点后，勇士的战斗力会加/减/乘一个正整数（根据节点而定）；每个勇士有初始战斗力和想占领的第一个节点。问，每个节点各有多少个勇士阵亡，每个勇士各占领了几个节点。

简要做法

每个节点搞个小根可并堆维护该节点所有勇士（包括一开始就在这的和爬上来的），当堆顶小于 $h$ 时弹出并更新答案，直到堆为空或者堆顶大于等于 $h$，然后再加/减/乘，合并到父亲。

加/减/乘：更新堆顶并打标记，在所有需要访问儿子的地方（弹出堆顶时/合并时）下传标记。

合并复杂度：每个勇士初始位置需要合并一次，每个节点合并到父亲要一次，$O((n+m)\log m)$；弹出复杂度：每个勇士最多被弹出一次，$O(m\log m)$；修改复杂度：除了下传标记外每次修改都是 $O(1)$ 的，所以是 $O(n)$；总复杂度：$O((n+m)\log m)$。

参考代码

#include <iostream>
#include <cstdio>
#include <cctype>
#include <algorithm>

using namespace std;

typedef long long ll;

ll read()
{
    ll out=0;
    int f=1;
    char c;
    for (c=getchar();!isdigit(c)&&c!='-';c=getchar());
    if (c=='-') f=-1,c=getchar();
    for (;isdigit(c);c=getchar()) out=out*10+c-'0';
    return out*f;
}

const int N=300010;

struct Node
{
    int ls,rs,d;
    ll val,add,mul;
    Node(){ls=rs=add=0;d=mul=1;}
} t[N];

int merge(int x,int y);
int pop(int x);
void madd(int u,ll x);
void mmul(int u,ll x);
void pushdown(int x);

void add(int u,int v);
void dfs(int u);

int head[N],nxt[N],to[N],cnt;
int n,m,p[N],f[N],a[N],dep[N],c[N],ans1[N],ans2[N];
ll h[N],b[N];

int main()
{
    int i;

    n=read();
    m=read();

    for (i=1;i<=n;++i) h[i]=read();

    for (i=2;i<=n;++i)
    {
        f[i]=read();
        add(f[i],i);
        a[i]=read();
        b[i]=read();
    }

    for (i=1;i<=m;++i)
    {
        t[i].val=read();
        c[i]=read();
        p[c[i]]=merge(i,p[c[i]]);
    }

    dfs(1);

    for (i=1;i<=n;++i) printf("%d\n",ans1[i]);
    for (i=1;i<=m;++i) printf("%d\n",ans2[i]);

    return 0;
}

void dfs(int u)
{
    int i,v;
    for (i=head[u];i;i=nxt[i])
    {
        v=to[i];
        dep[v]=dep[u]+1;
        dfs(v);
    }
    while (p[u]&&t[p[u]].val<h[u])
    {
        ++ans1[u];
        ans2[p[u]]=dep[c[p[u]]]-dep[u];
        p[u]=pop(p[u]);
    }
    if (a[u]) mmul(p[u],b[u]);
    else madd(p[u],b[u]);
    if (u>1) p[f[u]]=merge(p[u],p[f[u]]);
    else while (p[u])
    {
        ans2[p[u]]=dep[c[p[u]]]+1;
        p[u]=pop(p[u]);
    }
}

void add(int u,int v)
{
    nxt[++cnt]=head[u];
    head[u]=cnt;
    to[cnt]=v;
}

int merge(int x,int y)
{
    if (!x||!y) return x|y;
    if (t[x].val>t[y].val) swap(x,y);
    pushdown(x);
    t[x].rs=merge(t[x].rs,y);
    if (t[t[x].rs].d>t[t[x].ls].d) swap(t[x].ls,t[x].rs);
    t[x].d=t[t[x].rs].d+1;
    return x;
}

int pop(int x)
{
    pushdown(x);
    return merge(t[x].ls,t[x].rs);
}

void madd(int u,ll x)
{
    t[u].val+=x;
    t[u].add+=x;
}

void mmul(int u,ll x)
{
    t[u].val*=x;
    t[u].add*=x;
    t[u].mul*=x;
}

void pushdown(int x)
{
    mmul(t[x].ls,t[x].mul);
    madd(t[x].ls,t[x].add);
    mmul(t[x].rs,t[x].mul);
    madd(t[x].rs,t[x].add);
    t[x].add=0;
    t[x].mul=1;
}