社区讨论

当我试图这么写树剖(怎么才能这样调用啊TAT)

灌水区参与者 5已保存回复 15

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
15 条
当前快照
1 份
快照标识符
@lo8qcp4s
此快照首次捕获于
2023/10/27 22:50
2 年前
此快照最后确认于
2023/10/27 22:50
2 年前
查看原帖
这样写他会报这样一个错[Error] invalid use of non-static data member 'TreeChainSegmentation::inv'
CPP
#include<bits/stdc++.h>
#define slen(x) (r[x] - l[x] + 1)
using namespace std;

const int MAXN = 1e5 + 5;
const int MAXM = 2e5 + 5;

int inpt()
{
	int x = 0, f = 1;
	char ch;
	for(ch = getchar(); (ch < '0' || ch > '9') && ch != '-'; ch = getchar());
	if(ch == '-'){
		f = -1;
		ch = getchar();
	}
	do{
		x = (x << 3) + (x << 1) + ch - '0';
		ch = getchar();
	}while(ch >= '0' && ch <= '9');
	return x * f;
}

int n, m, rt, MOD; 
int w[MAXN];

struct TreeChainSegmentation {
	
	int hd[MAXN], to[MAXM], nxt[MAXM], tot = 0;
	void Add(int x, int y) {
		nxt[++tot] = hd[x];
		hd[x] = tot;
		to[tot] = y;
	}
	
	int siz[MAXN], dpt[MAXN], son[MAXN];
	int fa[MAXN];
	
	void dfs1(int x, int fath) {
		siz[x] = 1;
		dpt[x] = dpt[fath] + 1;
		fa[x] = fath;
		
		for(int i = hd[x]; i; i = nxt[i]) {
			int y = to[i];
			if(y == fath) continue;
			dfs1(y, x);
			siz[x] += siz[y];
		}
		if(siz[x] > siz[son[fath]]) {
			son[fath] = x;
		}
	}
//------------------------------------------------------------------------------------------------------就是这一坨
	int seg[MAXN], top[MAXN], inv[MAXN];
	int id = 0;
	
	void dfs2(int x, int tp) {
		seg[x] = ++id;
		inv[id] = x;
		top[x] = tp;
		
		if(!son[x]) return ;
		dfs2(son[x], tp);
		
		for(int i = hd[x]; i; i = nxt[i]) {
			int y = to[i];
			if(y == fa[x] || y == son[x]) continue;
			dfs2(y, y);
		}
	}
	
	struct SegmentTree {
		int l[MAXN << 2], r[MAXN << 2];
		int tag[MAXN << 2];
		int sum[MAXN << 2];
		
		void Build(int x, int L, int R) {
			l[x] = L, r[x] = R;
			if(L == R) {
				sum[x] = w[inv[L]];
				return ;
			}
			int mid = (L + R) >> 1;
			Build(x << 1, L, mid);
			Build(x << 1 | 1, mid + 1, R);
			sum[x] = (sum[x << 1] + sum[x << 1 | 1]) % MOD;
		}
//---------------------------------------------------------------------------------------------------------------------------
		void PushDown(int x) {
			if(tag[x]) {
				sum[x << 1] = (sum[x << 1] + 1ll * tag[x] * slen(x << 1) % MOD) % MOD;
				tag[x << 1] = (tag[x << 1] + tag[x]) % MOD;
				sum[x << 1 | 1] = (sum[x << 1 | 1] + 1ll * tag[x] * slen(x << 1 | 1) % MOD) % MOD;
				tag[x << 1 | 1] = (tag[x << 1 | 1] + tag[x]) % MOD;
				tag[x] = 0;
			}
		}
		void Change(int x, int L, int R, int v) {
			if(L <= l[x] && r[x] <= R) {
				tag[x] = (tag[x] + v) % MOD;
				sum[x] = (sum[x] + 1ll * v * slen(x) % MOD) % MOD;
				return ;
			}
			
			PushDown(x);
			int mid = (l[x] + r[x]) >> 1;
			if(L <= mid) {
				Change(x << 1, L, R, v);
			}
			if(R > mid) {
				Change(x << 1 | 1, L, R, v);
			}
			sum[x] = (sum[x << 1] + sum[x << 1 | 1]) % MOD;
		}
		
		int Ask(int x, int L, int R) {
			if(L <= l[x] && r[x] <= R) {
				return sum[x];
			}
			
			PushDown(x);
			int mid = (l[x] + r[x]) >> 1;
			int val = 0;
			if(L <= mid) {
				val = (val + Ask(x << 1, L, R)) % MOD;
			}
			if(R > mid) {
				val = (val + Ask(x << 1 | 1, L, R)) % MOD;
			}
			return val;
		}
	}str;
	
	void ChangeRoute(int x, int y, int v) {
		while(top[x] != top[y]) {
			if(dpt[top[x]] < dpt[top[y]]) {
				swap(x, y);
			}
			str.Change(1, seg[top[x]], seg[x], v);
			x = fa[top[x]];
		}
		
		if(dpt[x] < dpt[y]) {
			swap(x, y);
		}
		str.Change(1, seg[y], seg[x], v);
	}
	int AskRoute(int x, int y) {
		int val = 0;
		while(top[x] != top[y]) {
			if(dpt[top[x]] < dpt[top[y]]) {
				swap(x, y);
			}
			val = (val + str.Ask(1, seg[top[x]], seg[x])) % MOD;
			x = fa[top[x]];
		}
		
		if(dpt[x] < dpt[y]) {
			swap(x, y);
		}
		val = (val + str.Ask(1, seg[y], seg[x])) % MOD;
		return val;
	}
	
	void ChangeSubtree(int x, int v) {
		str.Change(1, seg[x], seg[x] + siz[x] - 1, v);
	}
	int AskSubtree(int x) {
		return str.Ask(1, seg[x], seg[x] + siz[x] - 1);
	}
}tr;

int main()
{
	
	n = inpt();
	m = inpt();
	rt = inpt();
	MOD = inpt();
	for(int i = 1; i <= n; i++) {
		w[i] = inpt() % MOD;
	}
	for(int i = 1; i < n; i++) {
		int x = inpt(), y = inpt();
		tr.Add(x, y);
		tr.Add(y, x);
	}
	
	tr.dfs1(rt, 0);
	tr.dfs2(rt, rt);
	tr.str.Build(1, 1, n);
	
	while(m--) {
		int op = inpt();
		if(op == 1) {
			int x = inpt(), y = inpt(), z = inpt();
			tr.ChangeRoute(x, y, z); 
			continue;
		}
		if(op == 2) {
			int x = inpt(), y = inpt();
			printf("%d\n", tr.AskRoute(x, y));
			continue;
		}
		if(op == 3) {
			int x = inpt(), z = inpt();
			tr.ChangeSubtree(x, z);
			continue;
		}
		if(op = 4) {
			int x = inpt();
			printf("%d\n", tr.AskSubtree(x));
		}
	}
	
	return 0;
}

回复

15 条回复,欢迎继续交流。

正在加载回复...