CF1685E The Ultimate LIS Problem 题解

Link

CF1685E The Ultimate LIS Problem

题意概述

给定长为 \(2n+1\) 的排列，对于 \(m\) 次交换操作，求出每次操作后一个能使排列 \(\text{LIS} \leq n\) 的循环移位 \(k\)，或报告无解。\((1 \leq n,m \leq 10^5)\)

Step 1

先不考虑操作，对一个排列考虑问题。

数据范围显然不支持我们 \(\text{DP}\) ，\(\text{LIS}\) 的限制看得我们一头雾水，索性 \(\text{Dirworth}\) 一下。

根据 \(\text{Dirworth}\) 定理，若 \(\text{LIS}=i\)，则覆盖原序列需要至少 \(i\) 个下降序列。

所以 \(\text{LIS} \leq n\) 等价于：原序列可以被 \(n\) 个以内的下降序列覆盖。

我们不需要最小化 \(\text{LIS}\)，所以构造一个 \(n\) 个下降序列的划分方式就足够了。

Step 2

因为排列长为 \(2n+1\)，考虑掏出一个数，剩下的两两配对完再把它插回去。

一定存在让这剩下 \(2n\) 个数能够两两配对成下降序列的循环移位。

更准确的说，一定存在让剩下 \(2n\) 个数中较大的 \(n\) 个与较小的 \(n\) 个两两配对的循环移位。

为什么呢？

不妨把较大的数看作左括号，较小的数看做右括号，问题转成求一个循环移位使其构成合法括号序列。

规定左括号权值为 \(1\)，右括号权值为 \(-1\)，考虑该权值的前缀和。

当该权值在每个位置的前缀和均 \(\geq 0\) 时，该序列较大的 \(n\) 个数恰好能与该序列较小的 \(n\) 个数两两配对。

对于任意一个前缀和最小的位置 \(i\)，把 \(1 \sim i\) 移位到末尾，得到的新序列都满足上面的约束。（不理解可以画折线图辅助理解）

如果觉得不够自然，可以先看看同场比赛的 C 题，思考方式有相似之处。

Step 3

现在考虑怎么把掏出来的数合法地插回去。

首先，刚才的移位对我们掏出来的数还是有影响的，我们大可不必真的把它掏出来，在计算括号权值的时候把它当成 \(0\) 就够了。

假如我们掏出来的数是 \(n+1\)，只要在括号序列中被括进了一对括号里，它就可以插进那对括号对应的下降序列中，答案 \(k\) 就是刚才移位的 \(i\)。

这并没有考虑完所有的有解情况，但性质足够优秀，不妨就钦定我们掏出来的数是 \(n+1\)。

对于剩下的情况，\(n+1\) 刚好不被任何一对括号括起来，意味着 \(n+1\) 不可能在下降序列的中间了，所以考虑 \(n+1\) 在两头的情况。

在刚才的移位后 \(n+1\) 可能还在序列的中间，看看能不能把它挪到两头来。

发现 \(n+1\) 两侧一定都是合法括号序列，直接挪到一起，\(n+1\) 就到了两头，正合我意。

当 \(n+1\) 在最右边时，如果序列中的 \([1,n]\) 不是单调上升的，即对于靠左的数 \(i\)，靠右的数 \(j\)，存在 \(1 \leq j < i \leq n\)，我们可以把 \(j\) 接到 \(i\) 那个下降序列的后面，这样原来和 \(i\) 匹配的大于 \(n+1\) 的数就空了出来。

那我们就可以把 \(n+1\) 接上去啦。

相应的，当 \(n+1\) 在最左边时，如果序列中的 \([n+2,2n+1]\) 不是单调上升的，我们也可以空出一个小于 \(n+1\) 的数，来和 \(n+1\) 接到一起。

\(n+1\) 在最左边的答案就是 \(i\) 加上左边挪动的那段合法括号序列长度，
在最右边就再加上 \(1\)。

如果两种接法都不可行，意味着至少有 \(n+1\) 个下降序列才能覆盖原序列的某个循环移位，报告无解。

Step 4

对于单个排列，我们已经能够在 \(\mathcal{O}(n)\) 的时间复杂度内应答，再考虑交换操作。

刚才的问题中，我们需要解决的子问题有：\(\pm 1\) 序列前缀和的 \(\text{min}\)，区间中 \([1,n]\),\([n+2,2n+1]\) 的数的单调性，均可用线段树维护带修答案。

总时间复杂度为 \(\mathcal{O}(m \log n)\)。