seq

对于 \(n\leq 15\) ，枚举每个子序列然后排序计算即可。时间复杂度 \(\mathcal O(2^nn\log n)\)。

对于 \(A_i\) 互不相同，可以枚举每个元素的贡献。即若 \(A_i\) 满足在某一子序列中排名第 \(A_i\) ，则有 \(1\) 的贡献。也就是当 \(1\sim A_i\) 都被选择时才能有贡献。而大于 \(A_i\) 的数选不选都可以，所以贡献为 \(2^{n-A_i}\)。

发现可以将原序列直接排序不影响答案结果，那么还是考虑每个元素的贡献求和。对于 \(A_i\) ，需要在前面 \(i-1\) 个数中选取恰好 \(A_i-1\) 个，后面 \(n-i\) 个数选不选都可以，预处理阶乘快速算组合数即可。时间复杂度 \(\mathcal O(n)\)。

lighthouse

我们发现，只有 $[1,ans] $ 中的灯塔都被照亮时才能够对答案有贡献，因此我们要做的就是在能照亮当前灯塔的前提下，尽量向右扩展能照到的灯塔数量。每次点亮一座灯塔后，向右找到第一座还没有被照亮的灯塔，重复此流程直到能够点亮的灯塔数用尽。

\(\mathcal O(n)\)，复杂度瓶颈在读入。

pile

题意是你可以依次对每个数选择放入一个初始为空的序列的开头或末尾，也可以放弃，但始终要保持手里的序列的元素递增。保证了每个数互不相等。

对于前 \(20\%\) 的数据，可以枚举每个数选或者不选，并容易判断其应该放在开头还是末尾。

对于 \(n\) 更大的情况，我们发现如果这道题去掉能插到开头或者能插到末尾的条件之一，就变成了一道单纯的最长上升（下降）子序列问题，可以从这里入手。

既要往前插入，也要往后插入，而且这两种操作混合在一起，这就导致问题很复杂。但我们发现往前插的数和往后插的数并不互相影响，因此我们可以设法把这两种操作分离开来。

对于每一种最后生成的单调的序列，我们可以把第一个插入的数看做中间数。那么单调队列中比它大的数和比它小的数，在原序列中的位置都在它后面。也就是在原序列中，由这个数到最后一个数所能形成的上升序列和下降序列拼接起来就是可行方案。那么问题转化为，在原序列中找一个数，使它到结尾的最长上升子序列和最长下降子序列的长度和最小。所以我们只要从结尾往前做最长上升和下降子序列即可，有暴力 dp \(O(n^2)\)（通过 \(70\%\) 的数据）和二分优化 dp \(O(n\log n)\)（通过 \(100\%\) 的数据）两种解决方法。

junior

首先你可以随便建立什么费用流模型来跑，或者写个二分图最大权匹配，可以拿下 70 分，估计也没人干。你有可能发现这是一道诈骗题，选择一个点$ (i,j)$ 意味着你可以点亮第 $ i$ 行或第 \(j\) 列，最后要求每行每列都被点亮。

这启发你给$ (i,j+n)$ 连一条费用为 \(a[i][j]\) 的边，现在问题变为有 \(n+m\) 个点，\(nm\) 条带权边，求最小生成基环森林。这玩意直接用 Kruskal 做就好了。就是排序后依次加入边，若加边后不满足图是基环森林那么就不加入。正确性可以用它做最小生成树的方法类似证明。\(\mathcal O(nm \log nm)\)。

contest

离线部分你可以看作从 \(1\) 走到 \(n\)，维护一个可重集，走到位置 \(i\) 就把集合中大于等于 \(a[i]\) 的加上 \(b[i]\)，在 $ l$ 处加入$ x，r$ 处取出 \(x\) 即可，因为相对大小不会改变，用你喜欢的数据结构维护即可。

考虑抽象一下问题变为你有 \(n\) 个分段一次函数，\(f_i(x)=x(x<=a_i),x+b_i(x>a_i)\)，每次询问就是要求 \(f_r(f_{r-1}(f_{r-2}(...(f_l(x))...)\) 的值。直接上线段树维护这个函数，长度为 m 的区间最终只会有 \(O(m)\) 个不同的段。实现就在线段树上把左儿子和右儿子的段做个双指针来复合起来，区间判一下交即可。

这个复合具体来说就是用左儿子的值域去复合右儿子的定义域，并且由于 \(b\) 随着 \(a\) 单调递增，是可以双指针而不是平方枚举的。维护好了函数之后就可以方便地处理询问了，每次询问去线段树拆分成的 \(\log\) 个结点里依次二分，找到对应段再加上去即可。\(\mathcal O(n \log n + q \log^2 n)\)，可以对照代码理解。