June 6, 2023
区间相交当然是很麻烦的。。前几天 CF #875 C 的时候还能用 hash 大法蒙混过关。。这次肯定不行了。。
我们先把这种情况放在最后处理，先写一个 28 分的代码。
这个性质可以指导我们进行离散化，从而方便使用各种数据结构。
可以简单调整得到，Vijos 1893 也考察了交换带来的具体影响。
所以在这种情况下我们可以不统计 未确定数和未确定数之间 的逆序对，因为必然是 0，但是这个性质不是通用的，我们不如先把所有数填出来，最后统一跑一遍求逆序对的代码，这样可以减少讨论。
这个是上面的性质的推广，显然对我们更有用。
所以综上所述，我们只需要开一棵线段树，记录当前填每个数时的代价，然后每次区间修改，区间求最小值即可。
最后只要考虑区间交就可以了。
我们最终的目标是处理出两个数组，A[] 表示所有已经被填的数，B[] 表示未填数的下界。
然后用线段树扫一遍，得到完整的 A[] 即可。
再看看性质 A，1 的情况那么全部只能填 1，直接填进 A[] 里，对于 0 的情况，我们希望继续利用 Lemma 3，从右向左扫描区间，尽可能晚的去填数。
最后去掉性质 A 只要按权值从大到小然后用并查集挖去每个阶段处理过的位置即可。
https://uoj.ac/submission/626775
Posted by
xiaodao
Category: 日常
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。