更好的阅读体验

博弈论基础，不懂 SG 函数 / 没接触过博弈论的看完 2.6 回来

#include<bits/stdc++.h>
#include<bits/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_table<int, 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];  // 为每个数字 x（1~32）维护一个数据结构，存储相邻两个 x 之间的区间的 SG 值
 
vector<int> g[34];         
int ne[34][N], last[34][N]; 
// ne[x][i]：位置 i 及之后第一个值为 x 的位
// last[x][i]：位置i及之前最后一个值为 x 的位置
 
bool cmp(pair<int, int> a, pair<int, 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];
        }
    }
    
    vector<pair<int, 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;
}

题意概括

题意就是给定一个序列和多组询问，每次询问一个子区间游戏的结果，游戏的规则是有一个数组集合，最开始只有原序列一个元素，由一方先走，删除数组集合中一个元素的所有某一个值 $x$，然后将序列按这些值分割成若干个序列，重新加入数组集合，不能操作就算输。

思路

首先发现这是一个公平组合游戏（双方操作相同，不能操作算输），考虑 DP 求 SG 函数。设 $f_{i, j}$ 为 $i \sim j$ 的游戏结果。DP 枚举当前选择数，暴力转移。时间复杂度 $O(n ^ 3V)$。

考虑优化。首先优化状态数，发现不能省掉一维，所以考虑证明状态数有限。我们考虑记忆化搜索实现，每次 DP 到的区间 $[i, j]$ 有几种情况：

• 左端点为查询的 $l$，且 $a_{j + 1}$ 在区间中不出现。
• 右端点为查询的 $r$，且 $a_{i - 1}$ 在区间中不出现。
• $a_{i - 1}$ 和 $a_{j + 1}$ 在区间中均不出现。
• 左端点为查询的 $l$，右端点为查询的 $r$。

前两类对于一个查询只有 $O(V)$ 种可能，总共 $O(qV)$ 种。最后一类有 $O(q)$ 种。

第二类考虑对于任意两个颜色 $x, y$，设他们的数量分别是 $cnt_x$ 和 $cnt_y$，则以它们为 $a_{i - 1}$ 和 $a_{j + 1}$ 的区间一共有 $O(cnt1 + cnt2)$ 种，总计：

$$\sum_{x = 1}^{32} \sum_{y = 1}^{32} cnt_x + cnt_y$$ $$= \sum_{x = 1}^{32} \sum_{y = 1}^{32} cnt_x + \sum_{x = 1}^{32} \sum_{y = 1}^{32} cnt_y$$$$= n \times 32 + n \times 32$$

总共 $O(nV)$ 种。

然后考虑优化转移，我们发现，一次转移分为两边的区间和中间的若干区间，中间的区间都满足 $a_{i - 1} = a_{j + 1}$。我们可以预处理所有中间的区间，然后支持快速查询区间和即可。

预处理的部分也要支持查询区间和，所以要求能动态单点加和区间和。考虑到一共有 $O(n)$ 个这样的区间，所以修改次数为 $O(n)$，查询次数为状态数乘上转移数 $O(nV ^ 2)$。使用分块平衡复杂组，单点加 $O(\sqrt n)$，区间查 $O(1)$。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <vector>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp> 

using namespace std;
using namespace __gnu_pbds;

const int N = 100010, B = 320;

int n, q;
int a[N];
gp_hash_table<int, int> f[N];
struct Data_Structure
{
	int w1[N], w2[N];
	int get(int x)
	{
		return (x - 1) / B + 1;
	}
	void modify(int x, int d)
	{
		int i = x;
		for (; (i - 1) % B != 0 && i <= n; i ++ ) w2[i] ^= d;
		if (i == n + 1) return;
		i --, i /= B, i ++ ;
		for (; i <= get(n); i ++ ) w1[i] ^= d;
	}
	int query(int l, int r)
	{
		if (l > r) return 0;
		int val1 = w2[l - 1] ^ w1[get(l - 1)], val2 = w2[r] ^ w1[get(r)];
		return val1 ^ val2;
	}
}t[34];
vector<int> g[34];
int ne[34][N], last[34][N];
int cnt;

bool cmp(pair<int, int> a, pair<int, int> b)
{
	return a.second - a.first < b.second - b.first;
}

int dfs(int l, int r)
{
	if (l > r) return 0;
	if (f[l].find(r) != f[l].end()) return f[l][r];
	cnt ++ ;
	bool st[34] = {0}, vis[34] = {0};
	for (int k = 1; k <= 32; k ++ )
	{
		int posl = ne[k][l], posr = last[k][r];
		cnt ++ ;
		if (posl > r) continue;
		st[k] = true;
		vis[dfs(l, posl - 1) ^ dfs(posr + 1, r) ^ t[k].query(posl + 1, posr - 1)] = true;
	}
	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);
			cnt += i;
			return f[l][r] = i;
		}
}

int main()
{
	scanf("%d%d", &n, &q);
	for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]), g[a[i]].push_back(i);
	vector<pair<int, int> > query;
	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];
	}
	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);
	while (q -- )
	{
		int l, r;
		scanf("%d%d", &l, &r);
		puts(dfs(l, r) ? "Toni" : "Jakov");
	}
	
	return 0;
}