求助8pts AC#11qwq
查看原帖
求助8pts AC#11qwq
716260
SegmentTree_楼主2023/12/28 23:18

看了前人的提醒和错误,改了很多还是8分

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lid (id << 1)
#define rid (id << 1 | 1)
const int N = 2e5 + 5;
struct node{
	int l, r;
	ll sum, mx, mn;
	int lazy;
}tr[N << 2];
int n, q;
int head[N << 1], nxt[N << 1], val[N << 1], to[N << 1], cccnnnttt, U[N], V[N], W[N], val1[N];
int dfn[N], rnk[N], hson[N], top[N], siz[N], fa[N], cnt, dep[N];
int a[N];
void add(int u, int v, int w){
	to[++cccnnnttt] = v;
	nxt[cccnnnttt] = head[u];
	val[cccnnnttt] = w;
	head[u] = cccnnnttt;
}
void pushup(int id){
	tr[id].sum = tr[lid].sum + tr[rid].sum;
	tr[id].mx = max(tr[lid].mx, tr[rid].mx);
	tr[id].mn = min(tr[lid].mn, tr[rid].mn);
}
void pushdown(int id){
	if (tr[id].lazy){
		tr[lid].sum = -tr[lid].sum;
		tr[rid].sum = -tr[rid].sum;
		tr[lid].mx = -tr[lid].mx;
		tr[rid].mx = -tr[rid].mx;
		tr[lid].mn = -tr[lid].mn;
		tr[rid].mn = -tr[rid].mn;
		swap(tr[lid].mx, tr[lid].mn);
		swap(tr[rid].mx, tr[rid].mn);
		tr[lid].lazy ^= 1;
		tr[rid].lazy ^= 1;
		tr[id].lazy = 0;
	}
}
void build(int id, int l, int r){
	tr[id].l = l;
	tr[id].r = r;
	tr[id].lazy = 0;
	if (l == r){
		tr[id].sum = a[l];
		tr[id].mx = a[l];
		tr[id].mn = a[l];
		return;
	}
	int mid = (l + r) >> 1;
	build(lid, l, mid);
	build(rid, mid + 1, r);
	pushup(id);
}
void modify(int id, int x, int y){
	if (tr[id].l == tr[id].r){
		tr[id].sum = y;
		tr[id].mx = y;
		tr[id].mn = y;
		return;
	}
	pushdown(id);
	int mid = (tr[id].l + tr[id].r) >> 1;
	if (x <= mid) modify(lid, x, y);
	else modify(rid, x, y);
	pushup(id);
}
void change(int id, int l, int r){
	if(tr[id].l>r||tr[id].r<l)return;
	if (l <= tr[id].l && tr[id].r <= r){
		tr[id].lazy ^= 1;
		tr[id].sum = -tr[id].sum;
		tr[id].mx = -tr[id].mx;
		tr[id].mn = -tr[id].mn;
		swap(tr[id].mn, tr[id].mx);
		return;
	}
	pushdown(id);
	int mid = (tr[id].l + tr[id].r) >> 1;
	if (r <= mid) change(lid, l, r);
	else if (l > mid) change(rid, l, r);
	else change(lid, l, mid), change(rid, mid + 1, r);
	pushup(id);
}
ll qsum(int id, int l, int r){
	if(tr[id].l>r||tr[id].r<l)return 0;
	if (l <= tr[id].l && tr[id].r <= r) return tr[id].sum;
	pushdown(id);
	int mid = (tr[id].l + tr[id].r) >> 1;
	if (r <= mid) return qsum(lid, l, r);
	else if (l > mid) return qsum(rid, l, r);
	else return qsum(lid, l, mid) + qsum(rid, mid + 1, r);
}
ll qmin(int id, int l, int r){
	if(tr[id].l>r||tr[id].r<l)return 1e18;
	if (l <= tr[id].l && tr[id].r <= r) return tr[id].mn;
	pushdown(id);
	int mid = (tr[id].l + tr[id].r) >> 1;
	if (r <= mid) return qmin(lid, l, r);
	else if (l > mid) return qmin(rid, l, r);
	else return min(qmin(lid, l, mid), qmin(rid, mid + 1, r));
}
ll qmax(int id, int l, int r){
	if(tr[id].l>r||tr[id].r<l)return -1e18;
	if (l <= tr[id].l && tr[id].r <= r) return tr[id].mx;
	pushdown(id);
	int mid = (tr[id].l + tr[id].r) >> 1;
	if (r <= mid) return qmax(lid, l, r);
	else if (l > mid) return qmax(rid, l, r);
	else return max(qmax(lid, l, mid), qmax(rid, mid + 1, r));
}
void dfs1(int u, int f){
	int maxson = 0;
	hson[u] = -1;
	siz[u] = 1;
	for (int i = head[u];i;i = nxt[i]){
		int v = to[i];
		if (v == f) continue;
		dep[v] = dep[u] + 1;
		fa[v] = u;
		val1[v] = val[i];
		dfs1(v, u);
		siz[u] += siz[v];
		if (siz[v] > maxson){
			maxson = siz[v];
			hson[u] = v;
		}
	}
}
void dfs2(int u, int t){
	top[u] = t;
	dfn[u] = ++cnt;
	rnk[cnt] = u;
	a[cnt] = val1[u];
	if (hson[u] == -1) return;
	dfs2(hson[u], t);
	for (int i = head[u];i;i = nxt[i]){
		int v = to[i];
		if (v != hson[u] && v != fa[u]) dfs2(v, v);
	}
}
ll qrangemax(int x, int y){
	ll ans = -1e18;
	while (top[x] != top[y]){
		if (dep[top[x]] < dep[top[y]]) swap(x, y);
		ans = max(ans, qmax(1, dfn[top[x]], dfn[x]));
		x = fa[top[x]];
	}
	if (dep[x] > dep[y]) swap(x, y);
	ans = max(ans, qmax(1, dfn[x] + 1, dfn[y]));
	return ans;
}
ll qrangemin(int x, int y){
	ll ans = 1e18;
	while (top[x] != top[y]){
		if (dep[top[x]] < dep[top[y]]) swap(x, y);
		ans = min(ans, qmin(1, dfn[top[x]], dfn[x]));
		x = fa[top[x]];
	}
	if (dep[x] > dep[y]) swap(x, y);
	ans = min(ans, qmin(1, dfn[x] + 1, dfn[y]));
	return ans;
}
ll qrangesum(int x, int y){
	ll ans = 0;
	while (top[x] != top[y]){
		if (dep[top[x]] < dep[top[y]]) swap(x, y);
		ans += qsum(1, dfn[top[x]], dfn[x]);
		x = fa[top[x]];
	}
	if (dep[x] > dep[y]) swap(x, y);
	ans += qsum(1, dfn[x] + 1, dfn[y]);
	return ans;
}
void changerange(int x, int y){
	while (top[x] != top[y]){
		if (dep[top[x]] < dep[top[y]]) swap(x, y);
		change(1, dfn[top[x]], dfn[x]);
		x = fa[top[x]];
	}
	if (dep[x] > dep[y]) swap(x, y);
	change(1, dep[x], dep[y]);
}
void modifynode(int u, int k){
	modify(1, dfn[u], k);
}
int main(){
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	int n;
	cin >> n;
	for (int i = 1;i < n;i++){
		int u, v, w;
		cin >> u >> v >> w;
		++u;++v;
		add(u, v, w);
		add(v, u, w);
		U[i] = u, V[i] = v, W[i] = w;
	}
	dep[1] = 1;
	dfs1(1, 0);
	dfs2(1, 1);
	build(1, 1, n);
	cin >> q;
	while (q--){
		string op;
		int u, v;
		cin >> op >> u >> v;
		if (op == "C"){
			int v1 = V[u], u1 = U[u];
			if (dep[v1] < dep[u1]) swap(v1, u1);
			//cout << v1 << '\n';
			modifynode(v1, v);
		}
		else if (op == "N"){
			++u;++v;
			changerange(u, v);
		}
		else if (op == "SUM"){
			++u;++v;
			cout << qrangesum(u, v) << '\n';
		}
		else if (op == "MAX"){
			++u;++v;
			cout << qrangemax(u, v) << '\n';
		}
		else{
			++u;++v;
			cout << qrangemin(u, v) << '\n';
		}
	}
	return 0;
} 
2023/12/28 23:18
加载中...