离散化问题求解

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, q, len, quest[2000005];
ll arr[5000005];
vector<ll> val;
unordered_map<ll, int> rns;

inline int lowbit(int x) {
    return x & -x;
}

void add(int x, int v) {
    for (int i = x; i <= len; i += lowbit(i))
        arr[i] += v;
}

int que(int x) {
    int ret = 0;
    for (int i = x; i; i -= lowbit(i))
        ret += arr[i];
    return ret;
}

struct edge {
    int to;
    ll l, r;
};
vector<edge> G[500005];

struct node {
    ll op, a, l = 114514, r = -114514;
} a[500005];

pair<ll, ll> ji(ll l1, ll r1, ll l2, ll r2) {
    return make_pair(max(l1, l2), min(r1, r2));
}

void dfs(int u, ll d) {
    for (auto edg : G[u]) {
        int v = edg.to;
        ll l = edg.l - a[u].op * a[u].a;
        ll r = edg.r - a[u].op * a[u].a;
        auto ans = ji(l, r, a[u].l + d, a[u].r + d);
        if (ans.second < ans.first) continue;
        a[v].l = ans.first - d;
        a[v].r = ans.second - d;
        dfs(v, d + a[u].op * a[u].a);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    // freopen("calc4.in", "r", stdin);
    // freopen("calc.out", "w", stdout);
    cin >> n >> q;
    for (int i = 2; i <= n; ++i) {
        ll f, l, r;
        cin >> f >> l >> r;
        G[f].push_back((edge){i, l, r});
    }
    for (int i = 1; i <= n; ++i) {
        char op;
        cin >> op >> a[i].a;
        a[i].op = (op == '+' ? 1:-1);
    }
    for (int i = 1; i <= q; ++i) {
        cin >> quest[i];
        val.push_back(quest[i]);
    }
    a[1].l = -2e18 - 5, a[1].r = 2e18 + 5;
    dfs(1, 0);
    for (int i = 1; i <= n; ++i) {
        val.push_back(a[i].l);
        val.push_back(a[i].r);
        val.push_back(a[i].r + 1);
    }
    sort(val.begin(), val.end());
    len = unique(val.begin(), val.end()) - val.begin();
    for (int i = 0; i < len; ++i)
        rns[val[i]] = i + 1;
    for (int i = 1; i <= n; ++i) {
        a[i].l = rns[a[i].l];
        a[i].r = rns[a[i].r];
    }
    for (int i = 1; i <= q; ++i)    
        quest[i] = rns[quest[i]];
    for (int i = 1; i <= n; ++i) {
        if (a[i].r < a[i].l)
            continue;
        add(a[i].l, 1);
        add(a[i].r + 1, -1);
    }
    for (int i = 1; i <= q; ++i)
        cout << que(quest[i]) << '\n';
    return 0;
}