题解：P12361 [eJOI 2024] 糖果售卖 / Sweets

· · 题解

题意

维护一棵带点权的树，初始时每个点的权值 w_i 为 0，支持以下操作：

题解

刚开始看到这道题时觉得很不可做。首先想到的是分块，对每个块维护排序后的块，区间加散块暴力重构。询问时，散块暴力，整块二分答案求解。时间复杂度为 O((n+q)\sqrt n\log n)，貌似只有 51 分。

看到 5\times 10^5 的 n，猜测是一只 \log。观察题目后发现一个细节之处，就是子树加上的数是正数！这意味着当某个点 i 满足 a_i\le w_i 后，它将永远符合条件。

于是我们考虑势能线段树，对于线段树每个节点维护最大值，先使每个点 i 的 w_i=-a_i。在每次子树加操作结束后递归去找新的符合条件的点。

递归过程中，若当前区间的最大值小于 0，那么这个区间中一定没有符合条件的点，直接返回。

最后就是统计答案，发现每个符合条件的点对答案的贡献的部分显然是以它为根的子树，直接用线段树维护即可。 最终的答案显然就是整个答案序列中的最大值。

时间复杂度

由于每个点只会被更新（由不符合条件变为符合条件）一次，n 个点就是 O(n\log n) 的复杂度。其他普通的线段树操作也是 O(n\log n) 的，所以总时间复杂度为 O(n\log n) 。

代码

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
#define rint register int
#define lb(i) (i&(-i))
const int N = 5e5 + 5;
int n, q, a[N], dfn[N], sz[N], rdfn[N], now;
vector<int> e[N];
char buf[83886000], *p1 = buf, *p2 = buf, ubuf[83886000], *u = ubuf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,83886,stdin),p1==p2)?EOF:*p1++)
inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
    for (; isdigit(ch); ch = getchar()) x = (x << 3) + (x << 1) + ch - '0';
    return x * f;
}
struct tree1 {
    int l, r, mx, tg;
#define l1(z) t1[z].l
#define r1(z) t1[z].r
#define mx1(z) t1[z].mx
#define tg1(z) t1[z].tg
} t1[N << 2];
struct tree2 {
    int l, r, mx, tg;
#define l2(z) t2[z].l
#define r2(z) t2[z].r
#define mx2(z) t2[z].mx
#define tg2(z) t2[z].tg
} t2[N << 2];
inline void build1(int k, int l, int r) {
    l1(k) = l, r1(k) = r;
    if (l == r) return;
    int mid = l + r >> 1;
    build1(k << 1, l, mid), build1(k << 1 | 1, mid + 1, r);
}
inline void pushdown1(int k) {
    if (tg1(k)) {
        mx1(k << 1) += tg1(k), mx1(k << 1 | 1) += tg1(k),
        tg1(k << 1) += tg1(k), tg1(k << 1 | 1) += tg1(k);
    }
    return (void)(tg1(k) = 0);
}
inline void Add1(int k, int x, int y, int v) {
    if (x <= l1(k) && r1(k) <= y) {
        mx1(k) += v, tg1(k) += v;
        return;
    }
    if (r1(k) < x || y < l1(k)) return;
    pushdown1(k), Add1(k << 1, x, y, v), Add1(k << 1 | 1, x, y, v);
    mx1(k) = max(mx1(k << 1), mx1(k << 1 | 1));
}
inline int Ans() {
    return mx1(1);
}
inline void build2(int k, int l, int r) {
    l2(k) = l, r2(k) = r;
    if (l == r) {
        mx2(k) = -a[rdfn[l]];
        return;
    }
    int mid = l + r >> 1;
    build2(k << 1, l, mid), build2(k << 1 | 1, mid + 1, r);
    mx2(k) = max(mx2(k << 1), mx2(k << 1 | 1));
}
inline void pushdown2(int k) {
    if (tg2(k)) {
        mx2(k << 1) += tg2(k), mx2(k << 1 | 1) += tg2(k),
        tg2(k << 1) += tg2(k), tg2(k << 1 | 1) += tg2(k);
    }
    return (void)(tg2(k) = 0);
}
inline void Add2(int k, int x, int y, int v) {
    if (x <= l2(k) && r2(k) <= y) {
        mx2(k) += v, tg2(k) += v;
        return;
    }
    if (r2(k) < x || y < l2(k)) return;
    pushdown2(k), Add2(k << 1, x, y, v), Add2(k << 1 | 1, x, y, v);
    mx2(k) = max(mx2(k << 1), mx2(k << 1 | 1));
}
inline void find(int k) {
    if (mx2(k) < 0) return;
    if (l2(k) == r2(k)) {
        Add1(1, l2(k), l2(k) + sz[rdfn[l2(k)]] - 1, 1);
        return void(mx2(k) = -1e9);
    }
    pushdown2(k), find(k << 1), find(k << 1 | 1),
    mx2(k) = max(mx2(k << 1), mx2(k << 1 | 1));
}
inline void dfs(int u) {
    dfn[u] = ++now, rdfn[now] = u, sz[u] = 1;
    for (int v : e[u]) dfs(v), sz[u] += sz[v];
}
int main() {
    ios::sync_with_stdio(0);
    cout.tie(0);
    cin.tie(0);
    n = read(), q = read();
    for (int i = 2, x; i <= n; i++) x = read(), e[x].push_back(i);
    for (int i = 1; i <= n; i++) a[i] = read();
    dfs(1);
    build1(1, 1, n), build2(1, 1, n);
    for (int u, x; q--;) {
        u = read(), x = read();
        Add2(1, dfn[u], dfn[u] + sz[u] - 1, x), find(1);
        cout << Ans() << endl;
    }
    return 0;
}

感谢管理员的审核，也感谢读者们的阅读。求赞 qaq。