Luogu6105 [Ynoi2010] y-fast trie

发表于 更新于 分类于 ， ， 阅读次数：

题意 ： 给定常数 ，你需要维护一个集合 ，初始时为空。

有 次操作：

  • 操作1：给出 ，插入一个元素 ，保证之前集合中没有 这个元素
  • 操作2：给出 ，删除一个元素 ，保证之前集合中存在 这个元素

每次操作结束后，需要输出从 集合中选出两个不同的元素的和 的最大值，或指出 集合中不足两个元素。

强制在线，， ，时限 。

将输入的所有 都先模 。

对于和，分 和 两类讨论。

对于 的情况，贡献是 ，只需取 中的最大值与次大值进行尝试。

对于 的情况，为每个数 找出 的最大的 ，则 是关于 的最佳方案，记为 。

每个元素只有一条出边，但可能有多条入边。显然，只有互指的元素对才可能是最优解。这种“互指关系”形成匹配（可能有元素未参与匹配），考虑动态维护这种匹配。

我们猜想修改对这些匹配的影响是 的。

  • 插入

    先找出和 配对的最优解 （）。查看 原来的出边 。若 ，则 改而指向 ，形成匹配 。

    若原来 ，插入 后变成 或，但 ， 必然不匹配。

  • 删除

    若没有匹配则直接删除。

    若有匹配 ，则将两者同时删除，再加入 。

注意可能存在相同的数值。

复杂度 。