ABC360 D F G
lzyqwq
·
·
个人记录
为啥只写这三个呢？因为是数据结构题。太菜了不会 E /ng。真的已经学 DS 学傻了。
D
对于蚂蚁 (i,j)，能相遇的充要条件是两者反向，且 \dfrac{|x_i-x_j|}{2}\le T，且 1 在 0 的左边。分别对 1,0 的权值建动态开点线段树，然后转化成二维偏序，绝对值容易去掉。枚举 i 之后只需要在反方向对应的线段树上数符合条件的 x_j 即可。
时空均 \mathcal{O}(N\log |V|)，V 为值域。
Code
F
考虑 (L_i,R_i) 对哪些 (l,r) 有贡献，这样的 (l,r) 形如一个矩形，问题转化为 \mathcal{O}(n) 次平面矩形加，然后求权值最大且 l 尽可能小且 r 尽可能小的点。像扫描线那样，扫描 l 一维，用动态开点线段树处理该维移动一单位时 r 一维的变化量即可。
线段树的节点信息要记当前 l 的 f 最大值，以及在哪个 r 取到。然后打擂取最值即可。注意一下 f 最大值为 0 的情况，此时答案为 (0,1)。
时空均 \mathcal{O}(N\log |V|)，V 为值域。
Code
G
答案大于等于原来的最长 LIS 长度。先求出这个。设 f_i/g_i 为以 i 为结尾 / 开头的最长 LIS 长度。
考虑一次修改，修改的位置一定要在新的 LIS 上否则不优。那么在新的 LIS 中，考虑它前面的一个位置 i。
修改 1 位置容易特判。
枚举这个 i。考虑修改的位置在 LIS 中的后继 j。应当满足 j>i+1，且 a_j>a_i+1，不然修改的位置权值不能连接二者。
对于满足这样的 j，应当取 g_j 最大者。就变成了一个二维限制的 \max。以下标为版本，a 为权值建主席树维护即可。
时空均 \mathcal{O}(N\log |V|)，V 为值域。
Code
上面这份被 hack 了。原因是这些限制涉及的指会超出值域。
原因其实是我将不合法的贡献处理为负无穷，但事实上是 0。导致有些情况寄掉。
于是将值域开到 2 倍就过了。为了防止线段树取中点操作溢出还开了 ll。
这个才是对的。
这种 DS 场多来点，我喜欢。