【题解】Game with Cards CF1539E dp — Qiuly

跟着做一遍 （挽救一下可怜我的发文量）

考虑设 $f_{i,j}$ 表示到第 $i$ 轮，是否有合法方案满足 $a=k_i$ 且 $b=k_j$ 。同样设 $g_{i,j}$ 表示到第 $i$ 轮，是否有合法方案满足 $b=k_i$ 且 $a=k_j$ 。

将转移分成以下几种：

• $k_i$ 和 $k_{i+1}$ 的得主不同：
  • $f_{i,j}\rightarrow g_{i+1,i}$：必要条件是 $b=k_{i+1},a=k_{i}$ 在第 $i+1$ 轮满足要求。
  • $g_{i,j}\rightarrow f_{i+1,i}$：必要条件是 $a=k_{i+1},b=k_{i}$ 在第 $i+1$ 轮满足要求。
• $k_i$ 和 $k_{i+1}$ 的得主相同：
  • $f_{i,j}\rightarrow f_{i+1,j}$：必要条件是 $a=k_{i+1},b=k_j$ 在第 $i+1$ 轮满足要求。
  • $g_{i,j}\rightarrow g_{i+1,j}$：必要条件是 $b=k_{i+1},a=k_j$ 在第 $i+1$ 轮满足要求。

线段树维护 $f,g$ 。第一种转移维护了线段树信息后看看能不能这么转移，然后再看看如果状态合法就插入线段树；第二种转移相当于先看看 $k_{i+1}$ 对应是否合法，然后满足必要条件的 $k_j$ 一定是一段连续的值域区间的，将其余部分直接清空即可。

时间复杂度 $O(n\log n)$ 。

代码咕了。