求调

P4211 [LNOI2014] LCA代码

同样的数据，本地（WSL2下的Ubuntu20.04环境g++9.4.0）跑没有任何问题，但提交到洛谷上就报错Runtime Error.Received signal 6: Aborted / IOT trap.

#include <bits/stdc++.h>
#define rint register int
#define ls (k << 1)
#define rs ((k << 1) | 1)
using namespace std;
const int N = 5e4 + 10, MOD = 201314;
int n, m;
long long ans[N];
struct node {int k, z, id;}; vector <node> ask[N];

//Graph
int cur, cnt, dfn[N], dep[N], fa[N], son[N], siz[N], top[N], head[N], to[N << 1], nxt[N << 1];

inline void add(int u, int v){
    to[++cur] = v, nxt[cur] = head[u], head[u] = cur;
    to[++cur] = u, nxt[cur] = head[v], head[v] = cur;
}

inline void DFS1(int u){
    son[u] = -1, siz[u] = 1;
    for (rint i = head[u]; i; i = nxt[i]){
        if (!dep[to[i]]){
            dep[to[i]] = dep[u] + 1;
            fa[to[i]] = u;
            DFS1(to[i]);
            siz[u] += siz[to[i]];
            if (son[u] == -1 || siz[to[i]] > siz[son[u]]) son[u] = to[i];
        }
    }
}

inline void DFS2(int u, int t){
    dfn[u] = ++cnt, top[u] = t;
    if (son[u] == -1) return;
    DFS2(son[u], t);
    for (rint i = head[u]; i; i = nxt[i]) if (to[i] != son[u] && to[i] != fa[u]) DFS2(to[i], to[i]);
}

//SegmentTree
struct SegmentTree {int l, r, len; long long w, tag;} tree[N << 2];

inline void up(int k) {tree[k].w = tree[ls].w + tree[rs].w;}

inline void down(int k){
    if (tree[k].tag){
        tree[ls].w += tree[k].tag * tree[ls].len;
        tree[ls].tag += tree[k].tag;
        tree[rs].w += tree[k].tag * tree[rs].len;
        tree[rs].tag += tree[k].tag;
        tree[k].tag = 0;
    }
}

inline void build(int k, int l, int r){
    tree[k].l = l, tree[k].r = r, tree[k].len = r - l + 1;
    if (tree[k].l == tree[k].r) return;
    int mid = (tree[k].l + tree[k].r) >> 1;
    build(ls, l, mid);
    build(rs, mid + 1, r);
}

inline void modify(int k, int l, int r){
    if (l <= tree[k].l && r >= tree[k].r) {tree[k].w += tree[k].len; tree[k].tag++; return;}
    down(k);
    int mid = (tree[k].l + tree[k].r) >> 1;
    if (l <= mid) modify(ls, l, r);
    if (r > mid) modify(rs, l, r);
    up(k);
}

inline long long query(int k, int l, int r){
    if (l <= tree[k].l && r >= tree[k].r) return tree[k].w;
    down(k);
    int mid = (tree[k].l + tree[k].r) >> 1; long long res = 0;
    if (l <= mid) res += query(ls, l, r);
    if (r > mid) res += query(rs, l, r);
    return res;
}

inline void modify_chain(int u, int v){
    while (top[u] != top[v]){
        if (dep[top[u]] >= dep[top[v]]) modify(1, dfn[top[u]], dfn[u]), u = fa[top[u]];
        else modify(1, dfn[top[v]], dfn[v]), v = fa[top[v]];
    }
    if (dep[u] < dep[v]) modify(1, dfn[u], dfn[v]);
    else modify(1, dfn[v], dfn[u]);
}

inline long long query_chain(int u, int v){
    long long res = 0;
    while (top[u] != top[v]){
        if (dep[top[u]] >= dep[top[v]]) res += query(1, dfn[top[u]], dfn[u]), u = fa[top[u]];
        else res += query(1, dfn[top[v]], dfn[v]), v = fa[top[v]];
    }
    if (dep[u] < dep[v]) res += query(1, dfn[u], dfn[v]);
    else res += query(1, dfn[v], dfn[u]);
    return res;
}

inline int read(){
    int x = 0;
    bool pos = true;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') pos = false;
    for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + c - '0';
    return pos ? x : ~(x - 1);
}

int main(){
    //freopen("P4211_1.in", "r", stdin);
    //freopen("P4211_1.ans", "w", stdout);

    n = read(), m = read();
    for (rint i = 1; i < n; ++i) {int f = read(); add(f, i);}
    for (rint i = 1; i <= m; ++i){
        int l = read(), r = read(), z = read();
        ask[l - 1].push_back({-1, z, i});
        ask[r].push_back({1, z, i});
    }
    dep[0] = 1;
    DFS1(0);
    DFS2(0, 0);
    build(1, 1, n);

    for (rint i = 0; i < n; ++i){
        modify_chain(0, i);
        for (node a : ask[i]) ans[a.id] += a.k * query_chain(0, a.z);
    }

    for (rint i = 1; i <= m; ++i) printf("%lld\n", (ans[i] + MOD) % MOD);
    return 0;
}