题解：AT_arc211_c [ARC211C] Forest

· · 题解

我们容易想到对于一个 # 区间我们只需要取这个区间的最大值，然后对于一个 . 区间也是这样的，我们记录其中的最大值和最大值数量，可以想到对于包含住 # 区间的两个 . 区间合并之后会变成一个大的 . 区间，这个区间的贡献就是大点区间的 \max，一次操作是正确的当且仅当操作后的 \max\{a_i\} 是全局最大值且恰好包含两个 . 区间和一个 # 区间，贡献的操作数是两个点区间的 \max 的个数相乘。我们把这些加起来即可。特别注意全局最大值是不能取到最左和最右两个不能取到的 # 区间的。