【bitset】【线段树】CF633G Yash And Trees 题解

CF633G

简单题。

先看到子树加和子树质数个数和，果断转换为 dfs 序进行处理。

既然有区间求和，考虑线段树。

若对于每一个节点维护一个 \(cnt\) 数组，用二进制数 \(x\) 来表示，即当 \(cnt_i = 1\) 时第 \(i\) 位为 \(1\)。设当前节点为 \(u\)，左右子节点分别为 \(ls\) 和 \(rs\)。发现 \(x_u = x_{ls} | x_{rs}\)。统计时，就是区间的所有 \(x\) 的按位或值 \(res\) 与质数数组所表示的二进制数 \(pr\) 的按位与后 \(1\) 的个数。然后考虑更改，令 \(v\) 为加的数，易得 x_u = (x_u << v & full) | (x_u >> (m - v))，其中 \(full = 2^m - 1\)，是防止溢出用的。

都到这一步了，不会还有人不知道怎么优化吧。

既然是二进制的数，用 bitset 进行优化即可。

时间复杂度：\(\mathcal{O}(\dfrac{nm\log n}{w})\)

代码：

const int N = 1e5 + 10, M = 1e3 + 10;
int n, m, Q, tot;
int a[N], b[N];
int tag[N << 2], d[N], siz[N], dfn[N], rdfn[N];
bitset<M> tr[N << 2], pr, f, ans;
int head[N], cnte;
struct edge {
	int v, nxt;
} e[N << 1];
void adde(int u, int v) {
	e[++cnte].nxt = head[u];
	e[cnte].v = v;
	head[u] = cnte;
}
 
void pushup(int u) {
	tr[u] = tr[u << 1] | tr[u << 1 | 1];
}
void pushdown(int u) {
	if (tag[u]) {
		tag[u << 1] = (tag[u << 1] + tag[u]) % m, tag[u << 1 | 1] = (tag[u << 1 | 1] + tag[u]) % m;
		tr[u << 1] = (tr[u << 1] << tag[u]) | (tr[u << 1] >> (m - tag[u]));
		tr[u << 1 | 1] = ((tr[u << 1 | 1] << tag[u]) & f) | (tr[u << 1 | 1] >> (m - tag[u]));
		tag[u] = 0;
	}
}
void build(int u, int l, int r, int *a) {
	if (l == r) {
		tr[u].reset();
		tr[u].set(a[l]);
		return;
	}
	int mid = l + r >> 1;
	build(u << 1, l, mid, a), build(u << 1 | 1, mid + 1, r, a);
	pushup(u);
}
void update(int u, int l, int r, int L, int R, int val) {
	if (L <= l && r <= R) {
		tag[u] = (tag[u] + val) % m;
		tr[u] = ((tr[u] << val) & f) | (tr[u] >> (m - val));
		return;
	}
	pushdown(u);
	int mid = l + r >> 1;
	if (L <= mid) update(u << 1, l, mid, L, R, val);
	if (mid < R) update(u << 1 | 1, mid + 1, r, L, R, val);
	pushup(u);
}
void query(int u, int l, int r, int L, int R) {
	if (L <= l && r <= R) {
		ans |= tr[u];
		return;
	}
	pushdown(u);
	int mid = l + r >> 1;
	if (L <= mid) query(u << 1, l, mid, L, R);
	if (mid < R) query(u << 1 | 1, mid + 1, r, L, R);
}
void dfs_init(int u, int f) {
	d[u] = d[f] + 1, siz[u] = 1, dfn[u] = ++tot, rdfn[tot] = u;
	for (int i = head[u], v; i != 0; i = e[i].nxt)
		if ((v = e[i].v) != f) {
			dfs_init(v, u);
			siz[u] += siz[v];
		}
}
 
int main() {
	ios
	cin >> n >> m;
	for (int i = 0; i < m; i++) f.set(i);
	for (int i = 2; i < m; i++) pr.set(i);
	for (int i = 2; i < m; i++)
		if (pr[i]) {
			for (int j = 2 * i; j < m; j += i)
				pr.reset(j);
		}
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		a[i] %= m;
	}
	for (int i = 1, u, v; i < n; i++) {
		cin >> u >> v;
		adde(u, v), adde(v, u);
	}
	dfs_init(1, 0);
	for (int i = 1; i <= n; i++) b[i] = a[rdfn[i]];
	build(1, 1, n, b);
	cin >> Q;
	while (Q--) {
		int opt, u, x;
		cin >> opt >> u;
		if (opt == 1) {
			cin >> x;
			update(1, 1, n, dfn[u], dfn[u] + siz[u] - 1, x % m);
		} else {
			ans.reset();
			query(1, 1, n, dfn[u], dfn[u] + siz[u] - 1);
			int res = (ans & pr).count();
			cout << res << "\n";
		}
	}
	return 0;
}