P14470 [COCI 2025/2026 #1] 松鼠 / Zagi - 洛谷谁点的博弈论补充了下之前写博弈论缺的对 SG 和 mex 的解释。0.分析完全没接触过博弈论的去看这个博客看完 2.6 就回来【博弈论和 SG 函数 | 那忘算 10】巴什博奕 尼姆博弈及其变种 威佐夫博弈附例题-CSDN博客1.流程当你删掉某个数后被夹在两个中间的区间就完全由“两个相邻的的位置”决定这样的区间总数是。所以只有靠近原始询问区间左右边界的那些段才可能和询问边界有关。每个询问、每种数最多贡献左右两段所以是。所以用记忆化搜索把算过的区间存下来状态数是可接受的。我们可以先求出两个数组来确定夹查询段两个相同值的位置。ne[x][i]位置 i 及之后第一个值为 x 的位置 last[x][i]位置 i 及之前最后一个值为 x 的位置接着求所有相邻相同值之间段的 SG 值。对于求区间的 SG 值的递归函数枚举每个数值用 ne 和 last 判断有无在区间出现过一对即两个及以上。如果出现过用区间内最靠近端点的两个将区间分成三段分别递归。递归出来的值就是上述的 “删掉某个值后所有小段异或的 SG 值”我们用数组记存。然后就可以枚举所有值看哪个没出现求 mex 了如果值是没出现过的最小整数而且这段查询区间刚刚好被两个值夹在中间这个区间就是相邻两个值之间的区间求出的 SG 值需要记存。2.算法好了现在最大的问题来了以上说的 SG 值要用什么数据结构存储查询对于每个数值都要记录特定的的异或值可以转为前缀异或和维护。数据范围考虑使用分块我们定义 w1,w2 分别为块间前缀和、块内前缀和。我们只有是刚刚好被两个值夹着的区间才记存异或值可以将作为记存位置先更新块内部分从到当前块末尾每个位置的 w2 都异或。更新块间部分从所在块到末尾块每个块的 w1 异或。这样每次查询只有右端点大于等于的时候才会用到的异或值。查询的时候计算的前缀异或和以及的前缀异或和两个一异或就是答案。别忘了记忆化搜索。3.代码数据 1e5考虑使用 pbds 里面的哈希数组不然被卡常#includebits/stdc.h #includebits/extc.h using namespace std; using namespace __gnu_pbds; const int N 1e5 10; const int B 320; int n; int a[N]; // 记忆化f[l][r] 存储区间 [l, r] 的 SG 值空区间为0 gp_hash_tableint, int f[N]; struct block { int w1[N], w2[N]; int get(int x) { return (x - 1) / B 1; } void modify(int x, int d) { if (d 0) return; int bid get(x); int r min(bid * B, n); for (int i x; i r; i) { w2[i] ^ d; } for (int i bid; i get(n); i) { w1[i] ^ d; } } int prefix(int pos) { if (pos 0) return 0; int b get(pos); return w1[b - 1] ^ w2[pos]; } int query(int l, int r) { if (l r) return 0; return prefix(r) ^ prefix(l - 1); } } t[34]; // 为每个数字 x1~32维护一个数据结构存储相邻两个 x 之间的区间的 SG 值 vectorint g[34]; int ne[34][N], last[34][N]; // ne[x][i]位置 i 及之后第一个值为 x 的位 // last[x][i]位置i及之前最后一个值为 x 的位置 bool cmp(pairint, int a, pairint, int b) { return a.second - a.first b.second - b.first; } int dfs(int l, int r) { // 计算区间 [l, r] 的 SG 值 if (l r) { return 0; } if (f[l].find(r) ! f[l].end()) { return f[l][r]; // 记忆化 } bool st[34] {0}; // st[k] 标记数字k是否在 [l,r] 中出现 bool vis[34] {0}; // vis[x] 标记后继 SG 值x是否可达 for (int k 1; k 32; k ) { int posl ne[k][l]; // [l,r] 中第一个k的位置 int posr last[k][r]; // [l,r] 中最后一个k的位置 if (posl r) continue; // 该数字不在区间中 st[k] true; int suma dfs(l, posl - 1); int sumb dfs(posr 1, r); int sumc t[k].query(posl 1, posr - 1); int sum suma ^ sumb ^ sumc; vis[sum] true; // 标记后继SG值 } // 求 mex未出现的最小非负整数 for (int i 0; ; i ) if (!vis[i]) { if (l ! 1 r ! n a[l - 1] a[r 1] !st[a[l - 1]]) { t[a[l - 1]].modify(r, i); // 以区间的右端点 r 作为存储位置存入 SG 值 } return f[l][r] i; } } int main() { ios::sync_with_stdio(false); cin.tie(0); int Q; cin n Q; for (int i 1; i n; i ) { cin a[i]; g[a[i]].push_back(i); // 记录每个值出现的位置 } memset(ne, 0, sizeof(ne)); memset(last, 0, sizeof(last)); for (int i 1; i 32; i ) { ne[i][n 1] n 1; for (int j : g[i]) { ne[i][j] last[i][j] j; } for (int j 1; j n; j ) { if (!last[i][j]) last[i][j] last[i][j - 1]; } for (int j n; j; j --) { if (!ne[i][j]) ne[i][j] ne[i][j 1]; } } vectorpairint, int query; for (int i 1; i 32; i ) for (int j 1; j g[i].size(); j ) query.push_back({g[i][j - 1] 1, g[i][j] - 1}); sort(query.begin(), query.end(), cmp); for (auto t : query) { dfs(t.first, t.second); // 先计算出这些区间的 SG 值并存入分块 } while (Q -- ) { int l, r; cin l r; cout (dfs(l, r) ? Toni : Jakov) \n; // SG ! 0 先手胜 } return 0; }