题目描述
小铭铭最近获得了一副新的桌游，游戏中需要用 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。注意每个骑士是单独计算的。也就是说一个骑士攻击一座城池，不管结果如何，均不会影响其他骑士攻击这座城池的结果。
现在的问题是，对于每个城池，输出有多少个骑士在这里牺牲；对于每个骑士，输出他攻占的城池数量。
Solution
看到大于等于某个数很容易想到堆，看到是树上问题很容易想到可并堆。
每个点维护一棵左偏树，存储在这个点的骑士。然后从下往上更新。
然后把所有小于城池生命值的骑士pop掉，同时记录有多少骑士死在这个城池了（ans1），哪些死了的骑士占领了几个城池（ans2）。
我们发现每座城池被占领后还会改变骑士的攻击力。其实这只要打一个懒标记在堆顶即可。
每次pop，和merge之前都要把懒标记下放进去。具体规则同线段树。
#include <iostream> #include <cstdio> #define int long long using namespace std; const int N = 300010; const int M = 300010; struct Leftist_Tree{ int val, dist, lson, rson, add, mul; }tr[N]; struct node{ int pre, to; }edge[N]; int head[N], tot; int n, m; int dep[N]; int h[N]; int fa[N], a[N], V[N]; int s[M], c[M]; int rt[N]; int ans1[N], ans2[M]; void add(int x, int v) { tr[x].val += v; tr[x].add += v; } void mul(int x, int v) { tr[x].val *= v; tr[x].add *= v; tr[x].mul *= v; } void push_down(int u) { if (tr[u].mul > 1) { mul(tr[u].lson, tr[u].mul); mul(tr[u].rson, tr[u].mul); tr[u].mul = 1; } if (tr[u].add) { add(tr[u].lson, tr[u].add); add(tr[u].rson, tr[u].add); tr[u].add = 0; } } int merge(int u, int v) { if (!u || !v) return u | v; if (tr[u].val > tr[v].val) swap(u, v); push_down(u); push_down(v); tr[u].rson = merge(tr[u].rson, v); if (tr[tr[u].lson].dist < tr[tr[u].rson].dist) swap(tr[u].lson, tr[u].rson); tr[u].dist = tr[tr[u].rson].dist + 1; return u; } int pop(int u) { push_down(u); return merge(tr[u].lson, tr[u].rson); } void dfs(int x) { for (int i = head[x]; i; i = edge[i].pre) { int y = edge[i].to; dep[y] = dep[x] + 1; dfs(y); rt[x] = merge(rt[y], rt[x]); } while (rt[x] && tr[rt[x]].val < h[x]) { ans1[x]++; ans2[rt[x]] = dep[c[rt[x]]] - dep[x]; rt[x] = pop(rt[x]); } if (a[x]) { mul(rt[x], V[x]); } else { add(rt[x], V[x]); } if (x == 1) { while (rt[x]) { ans2[rt[x]] = dep[c[rt[x]]] + 1; rt[x] = pop(rt[x]); } } } void Add(int u, int v) { edge[++tot] = node{head[u], v}; head[u] = tot; } int read() { int ret = 0, f = 1; char ch = getchar(); while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); } while (isdigit(ch)) { ret = (ret << 1) + (ret << 3) + ch - '0'; ch = getchar(); } return ret * f; } void write(int x) { if (x > 9) write(x / 10); putchar(x % 10 + '0'); } void print(int x) { if (x < 0) { x = -x; putchar('-'); } write(x); putchar(' '); } #undef int int main() { #define int long long n = read(); m = read(); for (int i = 1; i <= n; i++) h[i] = read(); for (int i = 2; i <= n; i++) { fa[i] = read(); a[i] = read(); V[i] = read(); Add(fa[i], i); } for (int i = 1; i <= m; i++) { s[i] = read(); c[i] = read(); tr[i].add = tr[i].dist = tr[i].lson = tr[i].rson = 0; tr[i].mul = 1; tr[i].val = s[i]; rt[c[i]] = merge(i, rt[c[i]]); } dfs(1); for (int i = 1; i <= n; i++) print(ans1[i]); for (int i = 1; i <= m; i++) print(ans2[i]); return 0; }