题意概述

这是一个双人轮流取物品的博弈问题，但具有以下特殊设定：

• 物品排成一个环（编号 0 到 n-1）
• 每轮：
  1. A 必须取走一个可用的物品 i
  2. B 可以选择取走 (i-d) mod n 或 (i+d) mod n 中的一个可用物品，或跳过
• 双方都希望最大化自己取走物品的价值和
• 物品价值是循环的：v[i] = w[i mod m]
• 有 q 次开关物品可用状态的操作，每次操作后询问：从当前可用物品集合开始游戏，B 能获得的最大价值和

数据范围极大：n 可达 10^16，m ≤ 2×10^4，q ≤ 10^5。

---

核心难点

1. n 极大：不能显式存储每个物品的状态
2. 环形结构：位置关系模 n 循环
3. 动态更新：每次操作只改变一个物品的可用状态
4. 博弈策略复杂：A 先手，但 B 有有限的反制选择

---

关键观察

1. 图的视角

将物品视为环上的点，每个点 i 有两条边连向 (i-d) mod n 和 (i+d) mod n。
实际上，B 的选择就是在 A 取走 i 后，可以取走与 i 距离为 d 的两个相邻点之一。

2. 独立链分解

由于每次移动步长为 d，整个环会分解为 gcd(n, d) 条独立的循环链。
每条链上的点按 +d 或 -d 跳跃可以遍历整条链。

重要性质：

• 每条链长度 L = n / gcd(n, d)
• 不同链之间在游戏过程中互不影响（因为 B 只能选距离 d 的点，不会跨链）

3. 单链上的博弈

考虑一条链上的点 p, p+d, p+2d, ...（模 n）。
当 A 在链上取走一个物品后，B 可以立即取走该物品在链上的前驱或后继（如果可用）。

这实际上形成了一种链上的对抗：A 取一个点，B 可以抢相邻点。

经过分析，在一条链上：

• 如果链长 L 是偶数，B 可以保证取到链上所有偶数位置（或所有奇数位置）的点
• 如果链长 L 是奇数，情况更复杂，但依然可以分析出 B 的稳定收益

4. 价值分布

由于 v[i] = w[i mod m]，且 m 较小，价值的分布具有周期性。
在长度为 L 的链上，点的价值序列也是周期性的，周期为 m / gcd(m, d)。

---

解法思路

步骤 1：链的划分

计算 g = gcd(n, d)，得到 g 条链，每条链长度 L = n/g。

步骤 2：链上博弈值计算

对于每条链，根据其可用物品的状态，可以计算出在这条链上游戏时 B 能获得的最大价值。

由于 m 较小，我们可以预处理每种“链状态模式”对应的 B 的收益。
链状态可以用一个长度为 L 的二进制串表示可用性，但 L 可能很大（最大 n/gcd(n,d)）。

突破口：
由于价值序列的周期性和链结构的周期性，实际上只需要考虑长度为 m' = m / gcd(m, d) 的段落的模式，然后复制到整个链上。

步骤 3：动态维护

每次操作只改变一个物品 x 的可用状态：

1. 确定 x 属于哪条链：chain_id = x mod g
2. 确定 x 在链上的位置：pos = floor(x / g)
3. 更新该链的状态，重新计算该链的 B 收益
4. 总答案 = 所有链的收益之和

步骤 4：高效更新

关键是要快速计算一条链在给定可用状态下的 B 收益。

这可以通过分析链上博弈的规律来实现：

• 实际上，在最优策略下，B 的收益可以表示为链上某些位置的价值之和
• 这些位置由链的奇偶性和可用状态决定
• 可以用线段树或类似结构维护链段的最大可能收益

但由于 n 极大，不能真的建线段树。
需要利用周期性：将链分成若干完整周期和残余部分，每段的收益可以预先计算或快速推导。

---

算法框架

1. 预处理：

   • 计算 g = gcd(n, d)
   • 计算每条链的价值序列（周期性）
   • 预处理各种“周期段”在不同可用状态下的 B 收益

2. 查询处理：

   • 维护每条链的可用状态（用字典或稀疏结构，因为每次只改一点）
   • 每次更新时，定位到对应链和周期段
   • 重新计算该链的总收益
   • 汇总所有链的收益作为答案

---

复杂度分析

• 链数 g ≤ n，但通常很小（gcd(n,d) 一般不大）
• 每条链的周期段数 ≤ m
• 每次更新只影响一个周期段，可以快速重新计算链收益
• 总复杂度 O(q × poly(m))，可以接受

---

总结

这道题的核心在于：

1. 发现环可以分解为独立链（通过 gcd(n,d)）
2. 利用价值周期性降低状态空间
3. 分析链上博弈的固定模式，避免模拟整个游戏过程
4. 动态维护链状态，支持单点更新和快速查询