竞赛算法解析：并查集维护、树形动态规划与组合数学推导
前缀极值与连通分量统计
观察可知，数组 \\(a\\) 中仅有前缀最大值会对连通性产生影响，其余元素要么处于孤立状态，要么必然与先前出现的前缀最大值连通。因此，我们只需针对数组 \\(b\\) 中的每个元素，确定其连接的前缀最大值区间，并利用并查集进行合并操作即可。若元素未与任何区间连通，则直接将其计入最终答案。
参考代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
#define lowbit(x) ((x) & (-(x)))
#define gc() (ptr1 == ptr2 && (ptr2 = (ptr1 = buffer) + fread(buffer, 1, 1 << 21, stdin), ptr1 == ptr2) ? EOF : *ptr1++)
char buffer[1<<21], *ptr1, *ptr2;
long long read_int() {
long long res = 0, neg = 0; char c = gc(); neg = (c == '-');
while (c < '0' || c > '9') c = gc(), neg |= (c == '-');
while (c >= '0' && c <= '9') res = res * 10 + c - '0', c = gc();
return res * (neg ? -1 : 1);
}
int total_a, total_b;
int seq_a[2000005], seq_b[2000005];
struct Fenwick {
int tree[2000005];
void update(int pos, int val) { for (; pos <= total_a; pos += lowbit(pos)) tree[pos] += val; }
int query(int pos) {
int res = 0;
for (; pos; pos -= lowbit(pos)) res += tree[pos];
return res;
}
} bit;
int sorted_idx[2000005];
int prefix_maxs[2000005], pm_cnt;
int valid_elems[2000005], val_cnt;
int final_ans;
int uf[2000005];
int find_root(int x) { return uf[x] == x ? x : (uf[x] = find_root(uf[x])); }
int main() {
freopen("delidish.in", "r", stdin);
freopen("delidish.out", "w", stdout);
int tc = read_int();
while (tc--) {
final_ans = pm_cnt = val_cnt = 0;
total_a = read_int(), total_b = read_int();
for (int i = 1; i <= total_a; i++) seq_a[i] = read_int(), sorted_idx[i] = i, uf[i] = i, bit.tree[i] = 0;
for (int i = 1; i <= total_b; i++) seq_b[i] = read_int();
sort(sorted_idx + 1, sorted_idx + total_a + 1, [](int x, int y) { return seq_a[x] < seq_a[y]; });
for (int i = 1, j = 1; i <= total_a; i++) {
while (j <= total_b && j <= seq_a[sorted_idx[i]]) bit.update(total_a - seq_b[j] + 1, 1), ++j;
if (bit.query(total_a - sorted_idx[i] + 1)) prefix_maxs[++pm_cnt] = sorted_idx[i];
else ++final_ans;
}
sort(prefix_maxs + 1, prefix_maxs + pm_cnt + 1);
for (int i = 1, cur_max = 0; i <= pm_cnt; i++) if (seq_a[prefix_maxs[i]] > cur_max) valid_elems[++val_cnt] = prefix_maxs[i], cur_max = seq_a[prefix_maxs[i]];
uf[val_cnt] = val_cnt;
for (int i = 1, j = 1; i <= total_b; i++) {
while (j <= val_cnt && i > seq_a[valid_elems[j]]) ++j;
int t = upper_bound(valid_elems + 1, valid_elems + val_cnt + 1, seq_b[i]) - valid_elems - 1;
if (j <= t) for (int x = find_root(j); x < t; x = find_root(x)) uf[x] = x + 1;
else ++final_ans;
}
for (int i = 1; i <= val_cnt; i++) final_ans += (find_root(i) == i);
cout << final_ans << "\n";
}
return 0;
}
树上排列组合与容斥原理
设 \\(f\_{i, j}\\) 表示在以 \\(i\\) 为根的子树中，划分为 \\(j\\) 个连续段的 \\(\\sum\\prod\\) 值。合并子树时，可以指定某些子树的连续段进行拼接，并乘上当前节点深度的贡献。但需注意，同一子树内的连续段不可合并。
- 容斥处理非法合并：在加入一棵子树时，在子树内部钦定若干非法合并，并乘以容斥系数求和。这样一来，包含非法合并的方案，其每个非法合并的子集都会因容斥系数的叠加而使得总贡献为 \\(0\\)，而合法方案的贡献恰好为 \\(1\\)，从而完成求解。
- 乘积贡献拆分：将乘积项拆解，问题转化为在每个 LCA 到根的路径上选取一个节点的方案数。基于此视角，相同子树的连续段合并变得合法，只是无需再乘上当前深度的贡献，直接转移即可。
参考代码（容斥做法）
#include <iostream>
#include <cstring>
#define int long long
using namespace std;
const int MOD = 1000000007;
inline void add_mod(int &x, int y) { (x += y) >= MOD ? (x -= MOD) : 0; }
int node_cnt;
int adj[505], nxt[505], dest[505], edge_cnt;
inline void add_edge(int u, int v) { dest[++edge_cnt] = v, nxt[edge_cnt] = adj[u], adj[u] = edge_cnt; }
int comb[505][505];
int dp[505][505], tmp_arr[505];
int sub_sz[505], parent[505];
int power[505][505];
void dfs(int u, int depth) {
dp[u][sub_sz[u] = 1] = 1;
for (int i = adj[u]; i; i = nxt[i]) {
int v = dest[i];
dfs(v, depth + 1);
memset(tmp_arr, 0, sizeof tmp_arr);
for (int a = 1; a <= sub_sz[v]; a++) {
for (int b = a + 1; b <= sub_sz[v]; b++) {
if ((b - a) & 1) add_mod(dp[v][a], MOD - dp[v][b] * comb[b - 1][b - a] % MOD * power[depth][b - a] % MOD);
else add_mod(dp[v][a], dp[v][b] * comb[b - 1][b - a] % MOD * power[depth][b - a] % MOD);
}
}
for (int a = 1; a <= sub_sz[u]; a++) {
for (int b = 1; b <= sub_sz[v]; b++)
add_mod(tmp_arr[a + b], dp[u][a] * dp[v][b] % MOD * comb[a + b][b] % MOD);
}
sub_sz[u] += sub_sz[v];
memcpy(dp[u], tmp_arr, sizeof tmp_arr);
}
for (int i = 1; i <= sub_sz[u]; i++) {
for (int j = i + 1; j <= sub_sz[u]; j++)
add_mod(dp[u][i], dp[u][j] * comb[j - 1][j - i] % MOD * power[depth][j - i] % MOD);
}
}
signed main() {
freopen("tree.in", "r", stdin);
freopen("tree.out", "w", stdout);
cin >> node_cnt;
for (int i = comb[0][0] = 1; i <= node_cnt; i++) {
for (int j = comb[i][0] = 1; j <= i; j++) comb[i][j] = (comb[i - 1][j - 1] + comb[i - 1][j]) % MOD;
for (int j = power[i][0] = 1; j <= node_cnt; j++) power[i][j] = power[i][j - 1] * i % MOD;
}
for (int i = 2; i <= node_cnt; i++) cin >> parent[i], add_edge(parent[i], i);
dfs(1, 1);
cout << dp[1][1] << "\n";
return 0;
}
参考代码（乘积拆分做法）
#include <iostream>
#include <cstring>
#define int long long
using namespace std;
const int MOD = 1000000007;
inline void add_mod(int &x, int y) { (x += y) >= MOD ? (x -= MOD) : 0; }
int node_cnt;
int adj[505], nxt[505], dest[505], edge_cnt;
inline void add_edge(int u, int v) { dest[++edge_cnt] = v, nxt[edge_cnt] = adj[u], adj[u] = edge_cnt; }
int comb[505][505];
int dp[505][505], tmp_arr[505];
int sub_sz[505], parent[505];
int power[505][505];
void dfs(int u, int depth) {
dp[u][sub_sz[u] = 1] = 1;
for (int i = adj[u]; i; i = nxt[i]) {
int v = dest[i];
dfs(v, depth + 1);
memset(tmp_arr, 0, sizeof tmp_arr);
for (int a = 1; a <= sub_sz[u]; a++) {
for (int b = 1; b <= sub_sz[v]; b++)
add_mod(tmp_arr[a + b], dp[u][a] * dp[v][b] % MOD * comb[a + b][b] % MOD);
}
sub_sz[u] += sub_sz[v];
memcpy(dp[u], tmp_arr, sizeof tmp_arr);
}
for (int i = 1; i <= sub_sz[u]; i++) {
for (int j = i + 1; j <= sub_sz[u]; j++)
add_mod(dp[u][i], dp[u][j] * comb[j - 1][j - i] % MOD);
}
}
signed main() {
freopen("tree.in", "r", stdin);
freopen("tree.out", "w", stdout);
cin >> node_cnt;
for (int i = comb[0][0] = 1; i <= node_cnt; i++) {
for (int j = comb[i][0] = 1; j <= i; j++) comb[i][j] = (comb[i - 1][j - 1] + comb[i - 1][j]) % MOD;
for (int j = power[i][0] = 1; j <= node_cnt; j++) power[i][j] = power[i][j - 1] * i % MOD;
}
for (int i = 2; i <= node_cnt; i++) cin >> parent[i], add_edge(parent[i], i);
dfs(1, 1);
cout << dp[1][1] << "\n";
return 0;
}
启发式合并与持久化线段树求颜色数
统计子树颜色种类数时，可以对子树内每种颜色维护其出现的最浅深度。随后建立线段树维护该最浅深度的频次数组，从而支持单点修改与区间求和，离线情况下即可解决。若需在线处理，可直接将 DSU on Tree 对桶的修改操作持久化。考虑到在线询问时能明确知道所需查询的具体颜色集合，最浅深度数组本身无需持久化。空间复杂度 \\(\\mathcal{O}(m \\log^2 m)\\)，时间复杂度 \\(\\mathcal{O}(nq + q \\log m + m \\log^2 m)\\)。
参考代码
#include <iostream>
#include <cstring>
#include <vector>
#include <array>
#include <set>
using namespace std;
#define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1<<21], *p1, *p2;
long long read_int() {
long long res = 0, neg = 0; char c = gc(); neg = (c == '-');
while (c < '0' || c > '9') c = gc(), neg |= (c == '-');
while (c >= '0' && c <= '9') res = res * 10 + c - '0', c = gc();
return res * (neg ? -1 : 1);
}
int n, m, q;
vector<int> adj1[200005], adj2[200005];
int col1[25], col2[200005];
int init_col[25];
array<int, 21> clr_record[1000005];
vector<int> queries_at_node[200005];
array<int, 5> q_info[1000005];
int dfs_seq[200005], rev_seq[200005], seq_cnt;
int sub_sz[200005], heavy_son[200005], par[200005];
int depth[200005];
void calc_heavy(int u, int p) {
depth[u] = depth[p] + 1;
sub_sz[u] = 1; par[u] = p;
rev_seq[dfs_seq[u] = ++seq_cnt] = u;
for (int v : adj2[u]) {
if (v != p) {
calc_heavy(v, u);
sub_sz[u] += sub_sz[v];
if (sub_sz[v] > sub_sz[heavy_son[u]]) heavy_son[u] = v;
}
}
}
int root[200005];
struct Node { int lch, rch, sum; } pool[86000005];
struct PersistSegTree {
int tot;
void insert(int &cur, int prev, int l, int r, int pos, int delta) {
pool[cur = ++tot] = pool[prev]; pool[cur].sum += delta;
if (l == r) return;
int mid = (l + r) >> 1;
if (pos <= mid) insert(pool[cur].lch, pool[prev].lch, l, mid, pos, delta);
else insert(pool[cur].rch, pool[prev].rch, mid + 1, r, pos, delta);
}
int query(int node, int l, int r, int ql, int qr) {
if (!node) return 0;
if (ql <= l && r <= qr) return pool[node].sum;
int mid = (l + r) >> 1;
if (qr <= mid) return query(pool[node].lch, l, mid, ql, qr);
if (ql > mid) return query(pool[node].rch, mid + 1, r, ql, qr);
return query(pool[node].lch, l, mid, ql, qr) + query(pool[node].rch, mid + 1, r, ql, qr);
}
} pseg;
multiset<int> depth_set[200005];
int cur_root;
int min_dep[100005];
void modify_node(int u, int type) {
pseg.insert(cur_root, cur_root, 1, m + 1, min_dep[col2[u]], -1);
if (type == -1) depth_set[col2[u]].erase(depth_set[col2[u]].find(depth[u]));
else depth_set[col2[u]].insert(depth[u]);
min_dep[col2[u]] = *depth_set[col2[u]].begin();
pseg.insert(cur_root, cur_root, 1, m + 1, min_dep[col2[u]], 1);
}
void add_subtree(int u, int type) { for (int i = dfs_seq[u]; i < dfs_seq[u] + sub_sz[u]; i++) modify_node(rev_seq[i], type); }
void dsu_on_tree(int u) {
for (int v : adj2[u]) if (v != par[u] && v != heavy_son[u]) dsu_on_tree(v), add_subtree(v, -1);
if (heavy_son[u]) dsu_on_tree(heavy_son[u]);
for (int v : adj2[u]) if (v != par[u] && v != heavy_son[u]) add_subtree(v, 1);
modify_node(u, 1);
root[u] = cur_root;
for (auto idx : queries_at_node[u]) for (int i = 1; i <= n; i++) clr_record[idx][i] = min_dep[clr_record[idx][i]];
}
int dep_alt[25], in_seq[25], out_seq[25], alt_cnt;
void preprocess_tree1(int u, int p) {
dep_alt[u] = dep_alt[p] + 1; in_seq[u] = ++alt_cnt;
for (int v : adj1[u]) if (v != p) preprocess_tree1(v, u);
out_seq[u] = alt_cnt;
}
bool vis[100005];
int main() {
freopen("tree.in", "r", stdin);
freopen("tree.out", "w", stdout);
n = read_int(), m = read_int(), q = read_int();
for (int i = 1; i < n; i++) {
int u = read_int(), v = read_int();
adj1[u].emplace_back(v);
adj1[v].emplace_back(u);
}
for (int i = 1; i < m; i++) {
int u = read_int(), v = read_int();
adj2[u].emplace_back(v);
adj2[v].emplace_back(u);
}
for (int i = 1; i <= 100000; i++) depth_set[i].insert(m + 1), min_dep[i] = m + 1;
for (int i = 1; i <= n; i++) col1[i] = read_int(), init_col[i] = col1[i];
for (int i = 1; i <= m; i++) col2[i] = read_int();
for (int i = 1; i <= q; i++) {
q_info[i][0] = read_int();
if (q_info[i][0] == 1) {
q_info[i][1] = read_int(), q_info[i][2] = read_int(), q_info[i][3] = read_int(), q_info[i][4] = read_int();
for (int j = 1; j <= n; j++) clr_record[i][j] = col1[j];
queries_at_node[q_info[i][2]].emplace_back(i);
} else {
q_info[i][1] = read_int(), q_info[i][2] = read_int();
col1[q_info[i][1]] = q_info[i][2];
}
}
calc_heavy(1, 0);
dsu_on_tree(1);
preprocess_tree1(1, 0);
memcpy(col1, init_col, sizeof init_col);
int last_ans = 0;
for (int i = 1; i <= q; i++) {
if (q_info[i][0] == 1) {
int x = q_info[i][1], y = q_info[i][2], a = q_info[i][3] ^ last_ans, b = q_info[i][4] ^ last_ans;
int res = pseg.query(root[y], 1, m + 1, depth[y], min(m, depth[y] + b));
for (int j = 1; j <= n; j++) if (in_seq[x] <= in_seq[j] && in_seq[j] <= out_seq[x] && dep_alt[j] - dep_alt[x] <= a) {
if (clr_record[i][j] > min(m, depth[y] + b)) {
res += !vis[col1[j]];
vis[col1[j]] = 1;
}
}
cout << (last_ans = res) << "\n";
for (int j = 1; j <= n; j++) vis[col1[j]] = 0;
} else col1[q_info[i][1]] = q_info[i][2];
}
return 0;
}
冒泡排序与快速划分的组合推导
快速排序的划分之后进行递归冒泡排序，与直接进行全局冒泡排序的总比较次数等价，因此只需计算冒泡排序的总遍历长度。针对每个下标 \\(i\\) 计算其贡献：将小于 \\(i\\) 的元素映射为 \\(0\\)，等于 \\(i\\) 的映射为 \\(1\\)，大于 \\(i\\) 的映射为 \\(2\\)。若 \\(0\\) 和 \\(1\\) 出现的最右位置为 \\(p\\)，则该位置贡献 \\(p - i\\) 次。若 \\(1\\) 不全在 \\(0\\) 之后，则会多贡献一次将 \\(1\\) 移至末尾的操作。推导公式如下：
用贡献为 \\(p - i + 1\\) 的方案数减去贡献为 \\(p - i\\) 的方案数：
\\(\\sum\\limits\_{i = 1}^n\\sum\\limits\_{j = i}^ni!(n - i)!\\binom{j - 1}{i - 1}(j - i + 1) - \\sum\\limits\_{i = 1}^n\\sum\\limits\_{j = i}^n(i - 1)!(n - i)!\\binom{j - 1}{i - 1}\\)
分别化简两部分：
\[\begin{equation}\begin{split} \sum\limits_{i = 1}^n\sum\limits_{j = i}^n(i - 1)!(n - i)!\binom{j - 1}{i - 1} &= \sum\limits_{i = 1}^n(i - 1)!(n - i)!\sum\limits_{j = i}^n\binom{j - 1}{i - 1} \\ &= \sum\limits_{i = 1}^n(i - 1)!(n - i)!\binom{n}{i} \\ &= \sum\limits_{i = 1}^nn!/i \\&= n!\sum\limits_{i = 1}^n\frac1{i} \\ \sum\limits_{i = 1}^n\sum\limits_{j = i}^ni!(n - i)!\binom{j - 1}{i - 1}(j - i + 1) &= \sum\limits_{i = 1}^ni!(n - i)!\sum\limits_{j = i}^n\binom{j - 1}{i - 1}j - \sum\limits_{j = i}^ni!(n - i)!\binom{j - 1}{i - 1}(i - 1) \\ &= \sum\limits_{i = 1}^ni!(n - i)!\sum\limits_{j = i}^n\binom{j - 1}{i - 1}j - i!(n - i)!(i - 1)\binom{n}{i} \\ &= \sum\limits_{i = 1}^ni!(n - i)!\sum\limits_{j = i}^n\binom{j - 1}{i - 1}j - n!(i - 1) \\ &= \sum\limits_{i = 1}^ni!(n - i)!(i\binom{n}{i} + (n - i + 1)\binom{n}{i} - \binom{n + 1}{i + 1}) - n!(i - 1) \\ &= \sum\limits_{i = 1}^n(n + 1)! - (n + 1)!/(i + 1) - n!(i - 1) \\ &= n(n + 1)! - \frac{n!n(n - 1)}{2} - (n + 1)!\sum\limits_{i = 1}^n\frac1{i + 1} \\ \end{split}\end{equation} \]
预处理调和级数倒数和后，即可 \\(\\mathcal{O}(1)\\) 计算单个 \\(n\\) 的答案。
参考代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#define int long long
using namespace std;
const int MOD = 998244353, inv2 = (MOD + 1) / 2;
int fact[10000005], har_sum[10000005], inv_elem[10000005];
void init_math(int limit) {
fact[0] = fact[1] = har_sum[1] = inv_elem[0] = inv_elem[1] = 1;
for (int i = 2; i <= limit; i++) {
fact[i] = fact[i - 1] * i % MOD;
inv_elem[i] = (MOD - MOD / i) * inv_elem[MOD % i] % MOD;
har_sum[i] = (har_sum[i - 1] + inv_elem[i]) % MOD;
}
}
int L_bound, R_bound;
signed main() {
freopen("tros.in", "r", stdin);
freopen("tros.out", "w", stdout);
cin >> L_bound >> R_bound;
init_math(R_bound + 2);
int result = 0;
for (int i = L_bound; i <= R_bound; i++) {
int cur = (i * fact[i + 1] % MOD + MOD - fact[i] * i % MOD * (i - 1) % MOD * inv2 % MOD + MOD - fact[i] * har_sum[i] % MOD + MOD - fact[i + 1] * (har_sum[i + 1] - 1) % MOD) % MOD;
result ^= cur;
}
cout << result << "\n";
return 0;
}
