AGC013F Two Faced Cards

题意 : 给出 个二元组，记为集合 。和 个整数，记为集合 。

有 个相互独立的操作。

每次会向 中加入一个二元组，然后你需要：

1. 对 中每一个二元组选定一个元素作为这个二元组的值，产生新集合

2. 将 中元素两两匹配（此时 ）。 能匹配 当且仅当 。

3. 如果匹配成功，获得的分数等于：第 1 步中，取第一个数作为值的二元组数量。

对于每个操作，求最大匹配分数，或指出无解。

，时限 。

---

首先将所有数关于 离散化，这样值域就变为 。

先不考虑操作。若给定 ，如何求出最大分数。

对于二元组 ，若 ，则必选 。

对于剩下的二元组，按照 排序，不难发现最优方案一定翻一个后缀，逐个判定即可。

• 如何判定序列 在任意排列后能否满足 ？

  利用辅助数组 ，对于 ，将 减一。

  对于 ，将 加一。

  若 全部非负，则存在合法方案。

• 于是，若将一个 的 翻面，则相当于将 加一。

---

现在考虑操作。

对于一个新加入的二元组 ，可以选择 或者 ，影响是将 的一个前缀 。

• 我们将问题转化为了：

  给出 数组，和若干个区间。

  每次再（独立地）进行一次前缀减，问至少选多少个区间加一可以使得整个数组非负。或指出无解。

设这次单独的前缀减为 ，对于每个 分别求出答案。

先求 的答案。

从后往前查看 中的元素，若遇到 的，则选取一个右端点大于等于它，且左端点尽量小的区间。这可以用堆来实现。

然后从小到大依次求 的答案。

当 增大时， 会减一，若这之后 ，则选择一个左端点小于等于它，且右端点尽量大的区间。这也用堆实现。

• 正确性理解：容易发现上述贪心得到的方案中，任意去掉一个区间，都会导致不合法。

区间加可以用差分实现。

复杂度为 。