树剖板子求调
查看原帖
树剖板子求调
933880
Code_quantum楼主2023/7/6 19:45

把讨论区看到的所有错误都改过了,但还是 0 pts。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<utility>
using namespace std;
#define int long long
#define lc (x << 1)
#define rc (x << 1 | 1)
#define mid ((l(x) + r(x)) >> 1)

const int N = 300005;
const int inf = 1e18;
struct edges{
	int to, next, w, id;
};
edges edge[2 * N];
int n, m, head[N], cnt = 0, vl[N];
int fa[N], size[N], dep[N], wson[N], top[N], go[N];
int idx = 0, inseg[N], ret[N];

namespace sgtree{
	struct segtree{
		int l, r, sum, maxn, minn;
		bool opp;
		#define l(x) tree[x].l
		#define r(x) tree[x].r
		#define sum(x) tree[x].sum
		#define opp(x) tree[x].opp
		#define maxn(x) tree[x].maxn
		#define minn(x) tree[x].minn
	};
	segtree tree[4 * N];
	void pushup(int x){
		sum(x) = sum(lc) + sum(rc);
		maxn(x) = max(maxn(lc), maxn(rc));
		minn(x) = min(minn(lc), minn(rc));
	}
	void build(int x, int l, int r){
		l(x) = l; r(x) = r;
		opp(x) = false;
		if(l == r){
			sum(x) = maxn(x) = minn(x) = vl[ret[l]];
			return;
		}
		build(lc, l, mid);
		build(rc, mid + 1, r);
		pushup(x);
	}
	void pushdown(int x){
		if(opp(x)){
			opp(lc) ^= 1;
			opp(rc) ^= 1;
			
			sum(lc) = - sum(lc);
			minn(lc) = - minn(lc);
			maxn(lc) = - maxn(lc);
			swap(minn(lc), maxn(lc));
			
			sum(rc) = - sum(rc);
			minn(rc) = - minn(rc);
			maxn(rc) = - maxn(rc);
			swap(minn(rc), maxn(rc));
			opp(x) = false;
		}
	}
	void modify(int x, int l, int r, int val){
		if(l <= l(x) && r(x) <= r){
			if(val == inf){
				opp(x) ^= 1;
				sum(x) = - sum(x);
				minn(x) = - minn(x);
				maxn(x) = - maxn(x);
				swap(minn(x), maxn(x));
			}else sum(x) = minn(x) = maxn(x) = val;
			return;
		}
		pushdown(x);
		if(l <= mid) modify(lc, l, r, val);
		if(r > mid) modify(rc, l, r, val);
		pushup(x);
	}
	segtree query(int x, int l, int r){
		if(l <= l(x) && r(x) <= r) return tree[x];
		pushdown(x);
		if(r <= mid) return query(lc, l, r);
		if(l > mid) return query(rc, l, r);
		segtree tmp, t1, t2;
		t1 = query(lc, l, r);
		t2 = query(rc, l, r);
		tmp.sum = t1.sum + t2.sum;
		tmp.maxn = max(t1.maxn, t2.maxn);
		tmp.minn = min(t1.minn, t2.minn);
		pushup(x);
		return tmp;
	}
};
using namespace sgtree;

namespace treediv{
	void dfs(int u, int ft){
		fa[u] = ft;
		dep[u] = dep[ft] + 1;
		size[u] = 1;
		for(int i = head[u]; ~ i; i = edge[i].next){
			int v = edge[i].to, w = edge[i].w, id = edge[i].id;
			if(v == ft) continue;
			dfs(v, u);
			go[id] = v;
			vl[v] = w;
			size[u] += size[v];
			if(size[v] > size[wson[u]]) wson[u] = v;
		}
	}
	void predo(int u, int tp){
		inseg[u] = ++ idx;
		ret[idx] = u;
		top[u] = tp;
		if(wson[u]) predo(wson[u], tp);
		for(int i = head[u]; ~ i; i = edge[i].next){
			int v = edge[i].to;
			if(v == fa[u] || v == wson[u]) continue;
			predo(v, v);
		}
	}
	void change(int x, int y){
		if(x == y) return;
		int fx = top[x], fy = top[y];
		while(fx != fy){
			if(dep[fx] < dep[fy]){
				swap(fx, fy);
				swap(x, y);
			}
			if(inseg[fx] <= inseg[x]) modify(1, inseg[fx], inseg[x], inf);
			x = fa[fx]; fx = top[x];
		}
		if(dep[x] > dep[x]) swap(x, y);
		if(inseg[x] + 1 <= inseg[y]) modify(1, inseg[x] + 1, inseg[y], inf);
	}
	int ask(int x, int y, int op){
		if(x == y) return 0;
		int fx = top[x], fy = top[y];
		int maxn = -inf, minn = inf, sum = 0;
		segtree tmp;
		while(fx != fy){
			if(dep[fx] < dep[fy]){
				swap(fx, fy);
				swap(x, y);
			}
			if(inseg[fx] <= inseg[x]){
				tmp = query(1, inseg[fx], inseg[x]);
				sum += tmp.sum;
				maxn = max(maxn, tmp.maxn);
				minn = min(minn, tmp.minn);
		    }
		    x = fa[fx]; fx = top[x];
		}
		if(dep[x] > dep[x]) swap(x, y);
		if(inseg[x] + 1 <= inseg[y]){
			tmp = query(1, inseg[x] + 1, inseg[y]);
			sum += tmp.sum;
			maxn = max(maxn, tmp.maxn);
			minn = min(minn, tmp.minn);
	    }
		if(op == 1) return sum;
		else if(op == 2) return maxn;
		else return minn;
	}
};
using namespace treediv;

void add_edge(int u, int v, int w, int id){
	edge[++ cnt].to = v;
	edge[cnt].w = w;
	edge[cnt].next = head[u];
	edge[cnt].id = id;
	head[u] = cnt;
}
signed main(){
	memset(head, -1, sizeof head);
	scanf("%lld", &n);
	for(int i = 1; i < n; i ++){
		int u, v, w;
		scanf("%lld %lld %lld", &u, &v, &w);
		u ++; v ++;
		add_edge(u, v, w, i);
		add_edge(v, u, w, i);
	}
	scanf("%lld", &m);
	dfs(1, 0);
	predo(1, 1);
	build(1, 1, idx);
	while(m --){
		string s; cin >> s;
		int d1, d2; scanf("%lld %lld", &d1, &d2);
		d1 ++; d2 ++;
		if(s == "C"){
			d1 --; d2 --;
			modify(1, inseg[go[d1]], inseg[go[d1]], d2);
		}
		else if(s == "N") change(d1, d2);
		else if(s == "SUM") printf("%lld\n", ask(d1, d2, 1));
		else if(s == "MAX") printf("%lld\n", ask(d1, d2, 2));
		else printf("%d\n", ask(d1, d2, 3));
	}
	return 0;
}
2023/7/6 19:45
加载中...