题解：P14521 【MX-S11-T2】加减乘除

· · 题解

容易发现对于树上的每个点，能到达它的 x 的值是一个区间，而这个区间是好求的。

假设我们已经求出了 fa_u 的区间 [L_{fa_u}],R_{fa_u}，而从根到 u 这条路径上要加上的 a 之和为 k，则合法的 x 需要满足：l_u\le x+k\le r_u 以及 L_{fa_u}\le x \le R_{fa_u}，取这两个区间的交集即可得到 u 的区间 [L_u,R_u]。

对于询问，就是要求有多少 i 满足 L_i\le x \le R_i，一个简单的做法是将所有的询问的 x 与所有的 L_i,R_i 放到一起离散化，那么一个数 y 的答案即为满足 L_i\le y 的 i 的数量减去满足 R_j<y 的 j 的数量，这两个值对应的是离散化后的一个前缀。

#include <bits/stdc++.h>
using namespace std;
int fa[500005];
vector<int>g[500005];
long long l[500005], r[500005];
long long L[500005], R[500005];
long long a[500005];
char op[500005];
long long b[2000005], c[2000005];
int k[2000005];
int cnt;
__int128 one = 1;

void dfs(int x, __int128 now) {
    if (L[x] > R[x])
        return;
    b[++cnt] = L[x], k[cnt] = 1;
    b[++cnt] = R[x], k[cnt] = 2;
    for (int y : g[x]) {
        long long ll = l[y], rr = r[y];
        //ll<=p+a[x]<=rr,L[x]<=p<=R[x]
        //p<=rr-a[x],p>=ll-a[x]
        __int128 pp = now;
        if (op[x] == '+')
            pp += a[x];
        else
            pp -= a[x];
        L[y] = max(one * L[x], ll - pp), R[y] = min(one * R[x], rr - pp);
        dfs(y, pp);
    }
}
long long as[1000005];
int xl[2000005], xr[2000005];
unordered_map<long long,int>da;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int n, q;
    cin >> n >> q;
    for (int i = 2; i <= n; i++) {
        cin >> fa[i] >> l[i] >> r[i];
        g[fa[i]].push_back(i);
    }
    for (int i = 1; i <= n; i++)
        cin >> op[i] >> a[i];
    R[1] = 1e18;
    L[1] = -1e18;
    dfs(1, 0);
    for (int i = 1; i <= q; i++) {
        cin >> as[i];
        b[++cnt] = as[i];
    }
    for (int i = 1; i <= cnt; i++)
        c[i] = b[i];
    sort(c + 1, c + cnt + 1);
    int nn = unique(c + 1, c + cnt + 1) - (c + 1);
    for (int i = 1; i <= cnt; i++) {
        b[i] = lower_bound(c + 1, c + nn + 1, b[i]) - c;
        if (k[i] == 1)
            xl[b[i]]++;
        if (k[i] == 2)
            xr[b[i]]++;
    }
    for (int i = 1; i <= nn; i++) {
        xl[i] += xl[i - 1];
        xr[i] += xr[i - 1];
        da[c[i]] = xl[i] - xr[i - 1];
    }
    for (int i = 1; i <= q; i++)
        cout << da[as[i]] << "\n";
}