2024.7.1 - 7.15

Question 1 - [ABC360G] Suitable Edit for LIS

给定一个长度为 \(n\) 的序列 \(A\)，你可以执行如下操作恰好一次，最大化 LIS 的长度：

• 选定一个下标 \(x\) 满足 \(1\leq x\leq n\)，选定一个任意的整数 \(y\)，然后将 \(A_x\) 替换为 \(y\)。

\(1\leq n\leq 2\times 10^5, 1\leq A_i\leq 10^9\)

首先，用线段树优化 DP 求出 \(f_i\) 表示以 \(A_i\) 结尾的最长 LIS 的长度，\(g_i\) 表示以 \(A_i\) 开头的最长 LIS 的长度。

如果修改没有任何作用，则答案为 \(f_i\) 的最大值。

如果尝试通过修改使得 LIS 增加 \(1\)，显然不会增加更多，首先，可以将 \(A_1\) 或 \(A_n\) 自由改动使得 LIS 可能增加 \(1\)，剩余情况则相当于求 \(\underset{1\leq i < j\leq n, j-i\ge 2, A_i +1\leq A_j-1}{\max} \{f_i+g_j+1\}\)。

再开一棵权值线段树，然后在 \(A_i + 1\) 处存储 \(f_i\) 的值维护即可。

Question 2 - [ABC360F] InterSections

给定 \(n\) 个区间 \(I_i = (L_i,R_i)\)，称 \((l_a,r_a)\) 与 \((l_b,r_b)\) 有交当且仅当 \(l_a < l_b < r_a < r_b\) 或 \(l_b < l_a < r_b < r_a\)，求一个区间 \((l,r)\) 使得：

• \(0\leq l < r\leq 10^9\)
• \((l,r)\) 与尽可能多的给定区间有交。

按照交的区间数量从大到小为第一关键字，\(l\) 从小到大为第二关键字，\(r\) 从小到大为第三关键字排序，找出第一个区间。

\(1\leq n\leq 10^5, 0\leq L_i < R_i \leq 10^9\)

首先，条件 \(l_a < l_b < r_a < r_b\) 或 \(l_b < l_a < r_b < r_a\) 可以看作矩形，其中 \((l,r)\) 可以看作坐标。

于是直接上扫描线，相当于维护权值线段树中的最大值及其位置，同时要求做到区间加，稍微维护一下即可。

注意坐标范围。