问题分析

有 $n$ 个城池构成一棵有根树，$m$ 个骑士从各自起始城池出发，沿着父节点路径向上攻击。每个城池 $i$ 有防御值 $h_i$，骑士需要战斗力 $\geq h_i$ 才能攻占。攻占后骑士战斗力会根据 $(a_i, v_i)$ 变化： 若 $a_i = 0$：战斗力增加 $v_i$ 若 $a_i = 1$：战斗力乘以 $v_i$

要求输出： 每个城池牺牲的骑士数量 每个骑士攻占的城池数量

算法思路

1. 整体框架

使用**左偏树（可并堆）**维护每个城池的骑士集合，从叶子到根逐层处理。

2. 关键数据结构

int rt[N];        // 每个城池的骑士堆根节点
lng add[N], tim[N]; // 懒标记：加法标记、乘法标记
int ls[N], rs[N], dep[N]; // 左偏树结构

3. 算法流程

初始化阶段

for (int i = 1; i <= m; i++) {
    scanf("%lld%d", s + i, c + i);
    tim[i] = 1;  // 重要：乘法标记初始化为1
    rt[c[i]] = merge(rt[c[i]], i); // 骑士加入起始城池
}

处理阶段（从叶子到根）

for (int i = n; i >= 1; i--) {
    // 淘汰战斗力不足的骑士
    while (rt[i] != -1 && s[rt[i]] < h[i]) {
        die[rt[i]] = i;  // 记录死亡位置
        rt[i] = merge(ls[rt[i]], rs[rt[i]]); // 移除该骑士
    }
    
    if (i == 1) break;  // 根节点特殊处理
    
    // 更新幸存骑士战斗力
    if (a[i] == 1) {
        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]);  // 下传标记
    
    // 幸存骑士前往父城池
    rt[fa[i]] = merge(rt[fa[i]], rt[i]);
}

4. 懒标记处理

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]] = s[ls[x]] * tim[x] + add[x];
    }
    // 右子树同理...
    
    add[x] = 0, tim[x] = 1;
}

标记应用顺序：先乘后加，即 $s' = s \times tim + add$

5. 左偏树合并

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[rs[x]] + 1;  // 维护左偏性质
    return x;
}

复杂度分析

时间复杂度：$O((n + m) \log m)$

• 每个骑士最多被合并、删除各一次
• 每次堆操作 $O(\log m)$ 空间复杂度：$O(n + m)$

输出计算

1. 城池牺牲数

for (int i = 1; i <= m; i++)
    ans[die[i]]++;
for (int i = 1; i <= n; i++)
    printf("%d\n", ans[i]);

2. 骑士攻占数

for (int i = 1; i <= m; i++)
    printf("%d\n", Dep[c[i]] - Dep[die[i]]);

其中：

• $Dep[c_i]$：骑士起始城池深度
• $Dep[die_i]$：骑士死亡城池深度
• 差值即为攻占的城池数量

关键技巧

1.懒标记：高效处理批量战斗力更新 2.从底向上处理：符合骑士攻击路径 3.左偏树：高效合并多组骑士 4.小根堆：快速淘汰弱者

样例验证

对于样例输入，算法能正确输出： 前 $n$ 行：各城池牺牲骑士数 后 $m$ 行：各骑士攻占城池数

该算法能够处理 $n, m \leq 3 \times 10^5$ 的大规模数据，通过懒标记和左偏树优化达到高效计算。