我宣布CF就是手速比赛，打CF不如打AC Saber。

· · 题解

对于一个点对 (x,t)，我们认为数组 a 合法当且仅当 \text{lower\_bound(a,\,x)\;=\;t}。

给定大小为 m 的点对集合 S=\{(x,k)\}，保证 x_i 和 k_i 分别互不相同，你需要：

  1. 找到 S'\subseteq S，使得存在一个长度为 n，值域为 [1,n] 的数组 a，其对 S' 中的所有点对都合法。最大化 |S'| 。
  2. 设上一问答案为 \text{Ans}，求出长度为 n，值域为 [1,n] 的数组 a 的个数，使得存在一个大小为 \text{Ans} 的集合 S'\subseteq S，满足 a 对 S' 中的所有点对都合法。对 \text{998244353} 取模。

Easy Version：1\leq m\leq n\leq 3000,\sum n\leq 10^4。

Hard Version：1\leq m\leq n\leq 3\times 10^5,\sum n\leq 10^6。

5s,256MB。

下文中为标记方便，对于 S/S' 中的数对 (a,b)，记 x_b=a。x 数组在数对未涉及的地方无定义。

我们从 \text{lower\_bound} 的过程入手，把二分的过程扔到线段树上去刻画：对一个值 p 进行二分时，首先把他丢到根节点上，然后与 a_{mid} 进行比较。假如有 x\leq a_{mid}，那就把他扔到左子树，否则把他扔到右子树。

我们定义集合 S' 是合法的，当且仅当存在一个对 S' 合法的序列 a。我们考虑如何判断一个集合 S' 是否是合法的：

还是从二分的过程考虑。不难发现， S' 中 x_{1\sim mid} 必然 \leq a_{mid}。反之亦然。所以说 a_{mid} 的取值在 \max\limits_{i=1}^{mid}\{x_i\} 到 \min\limits_{i=mid+1}^{n}\{x_i\} 之间。也即 \max\limits_{i=1}^{mid}\{x_i\}<\min\limits_{i=mid+1}^{n}\{x_i\}。

我建议你暂停想一想这意味着什么。如果你设计出了 \Omicron(n^4) 的 dp，那恭喜你，不过这个不重要。

你需要注意到的性质是：x 数组单调递增。 证明由于平凡所以省略。

因此第一问的答案就是容易求的了：不难发现就是 S 去除部分非法信息后，x 的最长上升子序列。

什么是不合法信息呢？不难发现只有 x_t=1 且 t 大于 1 时信息不合法，证明同样平凡所以省略。

我们仿照求 LIS 的过程作 dp。记 dp_i 表示线段树上区间全部在 [1,i] 内的节点答案。考虑转移：

dp_i=\sum dp_j\times \cdots \times[\text{LIS}_i=\text{LIS}_j+1 \land x_i>x_j]

其中 \cdots 为右端点从 j 扩展到 i 新扩展线段树节点的答案。对于每个被扩展的节点 [l,r]，其贡献为 \min\limits_{i=mid+1}^{r}\{x_i\}-\max\limits_{i=l}^{mid}\{x_i\}。其中若 \min 无定义则为 n+1，\max 无定义则为 1。

直接 dp 时间复杂度为 \Omicron(n^3)，可用前缀和等方法优化到 \Omicron(n^2\log n)。可以通过 Easy Version。

当 n\leq 3\times 10^5 时，\Omicron(n^2) 的时间复杂度不可接受，考虑数据结构优化。

优化的方式同样仿照 LIS。我们枚举 \text{LCA}(i,j)，不难发现 \text{LCA} 的左子树和右子树的贡献分别只与 j,\text{LCA} 和 i,\text{LCA} 有关。因此我们预处理出所有贡献。转移式变为如下状态：

dp_i=\sum dp_j\times wl_{j,\text{LCA}}\times wr_{i,\text{LCA}}\times [\text{LIS}_i=\text{LIS}_j+1 \land x_i>x_j] dp_i=\sum\limits_{\text{LCA}}wr_{i,\text{LCA}}\times\sum\limits_{j\in lson(LCA)} (dp_j\times wl_{j,\text{LCA}})\times [\text{LIS}_i=\text{LIS}_j+1 \land x_i>x_j]

可以线段树+扫描线转移，时间复杂度 \Omicron(n\log^2n)，可以通过此题。