跟着做一遍 (挽救一下可怜我的发文量)

考虑设 $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)$ 。

代码咕了。

分类: 文章

Qiuly

QAQ

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注