捞,求调树剖求求了
查看原帖
捞,求调树剖求求了
297778
badFlamesへ楼主2022/6/30 20:23

RT 求助,为什么调试显示线段树的p会越界访问

#include <bits/stdc++.h>
#define LL long long
#define pii pair <int, int>
#define inf 0x7f7f7f7f
using namespace std;
const int N = 3e5 + 5;

inline void File() {
    freopen("in.txt", "r", stdin);
    freopen("Ans.txt", "w", stdout);
}

inline int read() {
    int x = 0, w = 0; char ch = getchar();
    while(!isdigit(ch)) { w |= ch == 45; ch = getchar(); }
    while(isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
    return w ? -x : x;
}

int n, m, w[N], wx[N];
struct E { int x, y, z; }Edge[N];
struct F { int xi, yi; };
int dep[N], fa[N], siz[N], son[N], dfn[N], top[N], Ti;
vector <F> Link[N];

inline int S(E g) {
    return fa[g.x] == g.y ? g.x : g.y;
}

namespace RE_tree {
    #define lsp p << 1
    #define rsp p << 1 | 1
    #define lx lsp, l, r
    #define rx rsp, l, r
    #define midx mid = (t[p].l + t[p].r) >> 1
    #define contain l <= t[p].l && t[p].r <= r
    #define pushup t[p] = t[lsp] + t[rsp]

    struct T {
        int l, r;
        LL sum, mx, mn;
        //inline void init() { sum = 0, mx = -inf, mn = inf; }
    }t[N << 3 + N];
    int tag[N];

    T operator + (T L, T R) {
        return {L.l, R.r, L.sum + R.sum, max(L.mx, R.mx), min(L.mn, R.mn)};
    }

    inline void Fx(int p) {
        t[p].sum *= -1;
        LL Mn = t[p].mn, Mx = t[p].mx;
        t[p].mn = -Mx, t[p].mx = -Mn;
        tag[p] = 1;
    }

    inline void pushdown(int p) {
        if(!tag[p]) return;
        Fx(lsp); Fx(rsp);
        tag[p] = 0;
    }

    void build(int p, int l, int r) {
        t[p].l = l, t[p].r = r;
        if(l == r) { t[p] = {l, r, wx[l], wx[l], wx[l]}; return; }
        int mid = l + r >> 1;
        build(lsp, l, mid); build(rsp, mid + 1, r);
        pushup;
    }

    void Change(int p, int x, int v) {
        //if(x < t[p].l || t[p].r < x) return;
        if(t[p].l == x && t[p].r == x) { t[p].sum = t[p].mx = t[p].mn = v; return; }
        pushdown(p); int midx; x <= mid ? Change(lsp, x, v) : Change(rsp, x, v);
        pushup;
    }

    void Turn(int p, int l, int r) {
        if(l <= t[p].l && t[p].r <= r) { Fx(p); return; }
        pushdown(p); int midx;
        if(l <= mid) Turn(lx); if(mid < r) Turn(rx);
        pushup;
    }

    T query(int p, int l, int r) {
        printf("t[%d] = [%d, %d]\n", p, t[p].l, t[p].r);
        if(l <= t[p].l && t[p].r <= r) return t[p];
        pushdown(p); int mid = t[p].l + t[p].r >> 1;
        if(r <= mid) return query(lx); else if(l > mid) return query(rx);
        else return query(lx) + query(rx);
    }
}using namespace RE_tree;

namespace TreeLink_Subdivision {
    void dfsi(int u, int Fa, int Dep) {
        dep[u] = Dep, fa[u] = Fa, siz[u] = 1;
        for(int i = 0; i < (int)Link[u].size(); i++) {
            int v = Link[u][i].xi, wi = Link[u][i].yi;
            if(v == Fa) continue;
            dfsi(v, u, Dep + 1);
            siz[u] += siz[v];
            w[v] = wi;
            if(siz[son[u]] < siz[v]) son[u] = v;
        }
    }

    void dfsii(int u, int Top) {
        dfn[u] = ++Ti; wx[Ti] = w[u]; top[u] = Top;
        if(!son[u]) return; dfsii(son[u], Top);
        for(int i = 0; i < (int)Link[u].size(); i++) {
            int v = Link[u][i].xi; if(v == fa[u] || v == son[u]) continue;
            dfsii(v, v);
        }
    }

    inline void Updatex(int x, int y) {
        while(top[x] != top[y]) {
            if(dep[top[x]] < dep[top[y]]) swap(x, y);
            Turn(1, dfn[top[x]], dfn[x]);
            x = fa[top[x]];
        }
        if(dep[x] > dep[y]) swap(x, y);
        if(x != y) Turn(1, dfn[x] + 1, dfn[y]);
    }

    inline T Queryx(int x, int y) {
        T ans = {0, 0, 0, -inf, inf};
        while(top[x] != top[y]) {
            if(dep[top[x]] < dep[top[y]]) swap(x, y);
            ans = ans + query(1, dfn[top[x]], dfn[x]);
            x = fa[top[x]];
        }
        if(dep[x] > dep[y]) swap(x, y);
        return x != y ? ans + query(1, dfn[x] + 1, dfn[y]) : ans;
    }
}using namespace TreeLink_Subdivision;

signed main() {
#ifndef ONLINE_JUDGE
    File();
#endif
    scanf("%d", &n);
    for(int i = 1; i < n; i++) {
        int x, y, z;
        scanf("%d %d %d", &x, &y, &z);
        x++; y++;
        Link[x].push_back({y, z});
        Link[y].push_back({x, z});
        Edge[i].x = x, Edge[i].y = y;
    }

    dfsi(1, 0, 1);
    dfsii(1, 1);
    build(1, 1, n);

    //for(int i = 1; i <= n; i++) 
    //    printf("Node %d: [%d, %d, %d, %d, %d, %d]\n", i, dep[i], fa[i], siz[i], son[i], dfn[i], top[i]);

    cin >> m;
    while(m -- ) {
        char s[10]; int a, b;
        scanf("%s %d %d", s, &a, &b);
        if(s[0]=='C'){
            int g = S(Edge[a]);
            //Change(1, dfn[g], b);
        }
        else if(s[0] == 'N') {
            //Updatex(++a, ++b);
        }
        else if(s[0] == 'S') {
            printf("%lld\n", Queryx(++a, ++b).sum);
        }
        else if(s[0] == 'M' && s[1] == 'A') {
            printf("%lld\n", Queryx(++a, ++b).mx);
        }
        else if(s[0] == 'M' && s[1] == 'I') {
            printf("%lld\n", Queryx(++a, ++b).mn);
        }
    }
}
2022/6/30 20:23
加载中...