求问程序复杂度（MX-S11-T2）

#include <bits/stdc++.h>
#define int long long   
using namespace std; 

const int N = 5e5 + 5;                   

inline int rd() {
    int res = 0, f = 1; 
    char ch = getchar(); 
    while(ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar(); } 
    while('0' <= ch && ch <= '9') res = (res << 3) + (res << 1) + (ch - '0'), ch = getchar(); 
    return res * f; 
}

bool BEG_; 

bool FLA = 1; 

int n, q, a[N], hd[N], tot_e, f[N], ans, L[N], R[N];      
char op[N]; 

struct Edges {
    int nxt, to, l, r; 
} edge[N]; 

unordered_map<int, int> tr; 

bool END_; 

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

inline void add(int x, int d) {
    while(x <= (int)2000) tr[x] += d, x += lowbit(x); 
    return;  
} 

inline int qry(int x) {
    int res = 0ll; while(x) res += tr[x], x -= lowbit(x); 
    return res; 
}

inline void adde(int u, int v, int l, int r) {
    edge[++tot_e] = {hd[u], v, l, r}, hd[u] = tot_e; 
    return;  
}

void dfs(int u, int x) {
    ans++; 
    if(op[u] == '+') x += a[u]; 
    else x -= a[u]; 
    for(int i = hd[u]; i; i = edge[i].nxt) {
        int v = edge[i].to, l = edge[i].l, r = edge[i].r; 
        if(x < l || x > r) continue; 
        dfs(v, x);  
    }
    return; 
} 

void init(int u, int tmp, int ql, int qr) {
    // if(op[u] == '+') tmp += a[u]; 
    // else tmp -= a[u]; 
    // cout << u << ' ' << tmp << endl; 
    for(int i = hd[u]; i; i = edge[i].nxt) {
        int v = edge[i].to; 
        if(tmp >= 0) edge[i].l -= tmp, edge[i].r -= tmp; 
        else edge[i].l += tmp, edge[i].r += tmp; 
        if(edge[i].l < ql && u != 1ll) {
            edge[i].l = ql;   
        } 
        if(edge[i].r > qr && u != 1ll) {
            edge[i].r = qr; 
        } 
        // cout << i << ' ' << edge[i].l - 1000 << ' ' << edge[i].r - 1000 << endl; 
        add(max(edge[i].l, 0ll), 1ll);
        add(min(edge[i].r + 1, (int)(2000)), -1ll); 
        if(op[v] == '+') init(v, tmp + a[v], edge[i].l, edge[i].r);  
        else init(v, tmp - a[v], edge[i].l, edge[i].r); 
    } 
    return; 
}

signed main() {
    // cerr << (&BEG_ - &END_) / 1024.0 / 1024 << "MB\n"; 
    // freopen("calc4.in", "r", stdin); 
    // freopen("calc.out", "w", stdout); 
    n = rd(), q = rd(); 
    for(int i = 2, l, r; i <= n; i++) {
        f[i] = rd(), l = rd(), r = rd(); 
        if(f[i] != i - 1) FLA = 0; 
        if(max(n, q) <= 1000) adde(f[i], i, l, r); 
        else adde(f[i], i, l + 1000, r + 1000); 
    } 
    for(int i = 1; i <= n; i++) {
        op[i] = getchar(); a[i] = rd(); 
    } 
    if(max(n, q) <= 1000) {
        while(q--) {
            int x; x = rd(), ans = 0; 
            dfs(1, x); 
            printf("%lld\n", ans);            
        } 
        return 0; 
    }   
    if(op[1] == '+') init(1, a[1], 0, 0); 
    else init(1, -a[1], 0, 0);  
    while(q--) {
        int x; x = rd(); 
        x += 1000; 
        printf("%lld\n", qry(x) + 1ll);  
    }
    return 0; 
}