CLICK HERE(LINK)

$\large\text{Outline}$

• 小清新套路题。

$\large\text{Algorithm}$

• 套路一：满足条件的所有区间中求权值最大，要求时间复杂度 $O(n\log n)$，这种东西一般都是定一求一。
• 但两个序列不能选取到同一类型的元素并不方便我们直接使用扫描线+线段树做。

• 套路二：考虑答案包含 $A$ 序列中某位置 $p$，将 $B$ 序列中的点按对应类型在 $A$ 序列中所处位置可以划分出三类点：

  • 出现位置处于 $p$ 左侧，标记为 $1$。
  • 出现位置处于 $p$ 右侧，标记为 $-1$。
  • 在 $A$ 序列中没有出现，标记为 $0$。
• 当我们选择 $B$ 序列中某个区间时，$A$ 序列可选择的最大区间即为 $B$ 序列区间中标记为 $1$ 的元素在 $A$ 中出现位置的最大值与标记为 $-1$ 的元素在 $A$ 中出现位置的最小值构成的开区间。
• 因此当 $B$ 区间选择区间 $[l,r]$ 时，答案最大值为如下式子：

\[\begin{align*} ans_{l,r} &= (sum_a[(\min_{mark_i=-1\wedge i\in[l,r]}{pos_a[b[i]]})-1]\\ &-sum_a[\max_{mark_i=1\wedge i\in[l,r] }{pos_a[b[i]]}])+(sum_b[r]-sum_b[l-1]) \end{align*}\]

• 此时我们考虑维护 $B$ 序列上从右向左的扫描线 $l$ 表示区间左端点，考虑用线段树更新每个 $r$ 的 $ans_{l,r}$。
• 套路三：观察到所维护的式子为一个后缀最值，具有单调性，使用单调栈配合线段树即可。类似 $\texttt{CF526F Pudding Monsters}$。
• 最后的最后：这个必然经过的 $p$ 是什么呢？
• 显然可以分治一下强制规定 $p$ 为分治中心，时间复杂度 $O(n\log^2 n)$，过不太去。
• 由于答案至少是 $\max(sum_a[n],sum_b[n])$，我们在 $A,B$ 中各找到一个点使其为（带权 $x,y$ 后的）中点，如果要产生大于目前 $ans$ 的答案，两个序列至少有一个要选取经过中点的区间，我们可以发现这两个点至少有一个必须出现在答案方案中。

$\large\text{Notes}$

• 分析一环扣一环的套路题时须有耐心。