题目理解

我们有 $n$ 个回合，每个回合可以选择：

1. 施法：设置异常状态 $a_i$（清除之前状态）
2. 攻击：使用攻击模式 $b_i$，造成 $d_{b_i}$ 基础伤害 + 可能的暴击伤害 $c$，然后清除异常状态
3. 摸鱼：保持当前异常状态

暴击规则：当异常状态为 $p$ 时，使用攻击模式 $q$ 会额外造成 $c$ 伤害。

目标：最大化总伤害。

---

问题分析

关键观察

这是一个序列决策问题，需要决定每个回合的最优行动。

核心策略：在合适的异常状态下使用能触发高暴击的攻击。

难点：异常状态会被施法和攻击清除，需要精心安排状态维持和攻击时机。

---

代码解法详解

1. 数据结构设计

vector<pii> s[N], t[N];  // 分别存储小集合和大集合的暴击规则
ll dp[N], A[N];         // dp[i]: 前i回合最大伤害，A[g]: 特定攻击模式的最佳值
int ls[N];              // ls[p]: 异常状态p最近一次出现的位置

2. 阈值分治策略

根据暴击规则的数量分治：

• 小集合（$\le S$）：直接枚举所有可能的暴击组合
• 大集合（$> S$）：预处理最佳攻击时机

for (int i = 1; i <= m; i++)
    if (s[g[i]].size() > S)
        t[p[i]].emplace_back(g[i], c[i]);

3. 动态规划转移

对于每个回合 $i$：

情况1：小集合攻击模式

for (auto &x : s[b[i]])
    if (ls[x.fi])  // 如果该异常状态之前出现过
        dp[i] = max(dp[i], dp[ls[x.fi] - 1] + x.se);

在最近一次设置异常状态 $p$ 后，直到当前回合保持状态，然后使用攻击触发暴击。

情况2：大集合攻击模式

dp[i] = max(dp[i], A[b[i]]);

直接从预处理的最佳值中获取。

基础伤害

dp[i] += d[b[i]];

更新状态跟踪

ls[a[i]] = i;  // 记录异常状态a[i]的最新位置

更新大集合攻击机会

for (auto &x : t[a[i]])
    A[x.fi] = max(A[x.fi], dp[i - 1] + x.se);

在当前回合设置异常状态后，为后续可能的大集合攻击模式记录最佳起点。

---

算法正确性分析

状态维持策略

• ls[p] 记录了异常状态 $p$ 最近一次被设置的位置
• 在 ls[p] 和当前回合之间，状态 $p$ 一直保持（除非被其他施法或攻击清除）
• 这保证了暴击条件的正确判断

转移方程含义

• dp[ls[x.fi] - 1] + x.se：在设置状态 $p$ 之前的最优解 + 暴击伤害
• 这表示从设置状态开始保持，直到当前回合攻击触发暴击

---

样例分析

对于样例：

n=4, m=1, x=2, y=2
d = [10, 1]
行动序列：
(2,1), (1,1), (1,2), (2,2)  
暴击规则：(2,2,1000000000)

执行过程：

• 回合1：设置状态2，ls[2]=1
• 回合2：设置状态1，ls[1]=2
• 回合3：攻击模式2（小集合），找到状态2在位置1，计算暴击 dp[3] = max(..., dp[0] + 1e9) = 1e9，加上基础伤害1 → 1e9+1
• 回合4：攻击模式2，加上基础伤害1 → 1e9+2

---

复杂度分析

• 预处理：$O(m)$
• DP转移：
  • 小集合：$O(S)$ 每个回合，总 $O(nS)$
  • 大集合：$O(\frac{m}{S})$ 每个回合，总 $O(n \cdot \frac{m}{S})$
• 总复杂度：$O(nS + \frac{nm}{S})$，取 $S = \sqrt{m}$ 时为 $O(n\sqrt{m})$

对于 $n, m \le 2\times 10^5$，可接受。

---

算法标签

• 动态规划
• 阈值分治
• 序列决策
• 数据结构优化
• 状态跟踪

---

总结

这道题的解法核心是：

1. 状态跟踪：记录每个异常状态的最新设置位置
2. 阈值分治：根据暴击规则数量采用不同策略
3. 时机优化：在保持异常状态的连续区间内安排暴击攻击
4. DP设计：dp[i] 表示前 $i$ 回合的最优解，支持高效状态转移

通过巧妙的阈值分治和状态跟踪，将复杂的序列决策问题转化为高效的可计算模型。