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);
}
}
}