P6406 [COCI2014-2015#2] Norma【题解】
Phrvth
·
·
题解
\mathcal{Update}\ at\ 2023.10.12
Question
给出一个序列 A，定义 f(l,r) 为
f_{l,r}=(r-l+1)\times \max(l,r) \times \min(l,r)
其中 \max(a,b) 表示 A_a \sim A_b 的最大值，\min 同理。
求
\sum_{l=1}^n \sum_{r=l}^n f(l,r)
Solution
对于这种给一个序列求每个二元组的值，一般考虑分治。
那我们考虑当前要处理的区间为 [L,R]，mid 为其中点，我们递归求解 [L,mid] 和 [mid + 1,R]，现在我们只需要处理 l\in[L,mid],r\in(mid,R] 的二元组即可。
考虑枚举每一个 l，计算这个 l 对答案产生的贡献。
容易想到，这个贡献分为三类。
- 右区间被左区间的最大最小值完全包裹着
- 右区间有一个最值被左区间包裹着
- 右区间与左区间没关系
我们形式化这些情况，设 \min(l, mid) 对右边产生的最远的影响为 a，\max(l,mid) 对右边产生的最远的影响为 b。
然后因为好处理，我们考虑设 w1 为 \min(a,b)，w2 为 \max(a,b)，然后分情况考虑。
这个区间的最大值分明就是 \max(l,mid) 和 \min(l,mid)，所以这个区间对答案产生的贡献为：
\sum_{i=mid+1}^{w1} f(l,i)=\max(l,mid) \times \min(l,mid) \times \sum_{i=mid+1}^{w1} (i-l+1)
然后右边的求和符号明显是等差数列，我们使用小学知识把他拆掉最后化简，得到：
\sum_{i=mid+1}^{w1} f(l,i)=\max(l,mid) \times \min(l,mid) \times \frac{w_1+mid-2l+3}{2}
然后又分成两种情况。
-
a<b
这种情况呢，可以使用最大值，但是最小值使用不了。
这里有个重点，在分治问题中，mid 是极其重要的。
比如这里，我们考虑把答案拆成两部分，即为 [l,mid] 和 (mid,w2] 去求解。
答案即为：
\sum_{r=w_1+1}^{w_2} f(l,i)=(\sum_{w1+1}^{w2}(mid-l+1)\times \min(mid+1,i) \times \max(l,mid)) + (\sum_{w1+1}^{w2}(i-(mid+1)-1) \times \min(mid+1,w2) \times max(l,mid))
看起来很长，但是很简单，第一个大括号是求 [l,mid] 的贡献，因为右边的最小值才是整个区间的最小值，所以乘的是右区间的最小值和左区间的最大值。
最后通过乘法分配律把两个区间拼在一起得到答案。
我们对这个式子进行化简。
\sum_{r=w1+1}^{w2} f(l,i)=(mid-l+1) \times \max(l,mid) \times \sum_{i=w1+1}^{w2} \min(mid+1,i)+\max(l,mid) \times \sum_{w1+1}^{w2}(i-mid) \times \min(mid+1,i)
然后对里面的求和符号我们可以使用前缀和拆开。
我们令 S1_{i,0} 表示前面那一段的前缀和，S1_{i,1} 表示后面的那段的前缀和，即
\begin{aligned}
S1_{i,0} &= \sum_{j=mid+1}^i \min(mid+1,j)\\
S2_{i,0} &= \sum_{j=mid+1}^i \min(mid_1,j) \times (j-mid)
\end{aligned}
然后这一段的贡献可以化简为：
\sum_{r=w1+1}^{w2} f(l,i)=\max(l,mid)\times ((mid-l+1)\times (S1_{w2,0} - S1_{w1,0})+(S1_{w2,1} - S1_{w1,1}))
- a>b
同理的，可以推出贡献为：
\sum_{r=w1+1}^{w2} f(l,i)=\min(l,mid)\times ((mid-l+1)\times (S2_{w2,0} - S2_{w1,0})+(S2_{w2,1} - S2_{w1,1}))
这段区间完全和上面的处理方法一样，只是前缀和的数组需要变一下，我觉得读者们应该都懂吧。
\sum_{r=w2+1}^{R} f(l,i)=(S3_{R,1}-S3_{w2,1}) + ((mid-l+1)+(S3_{R,0}-S3_{w2,0}))
至此，我们的全部情况都讨论清楚了，接下来有几个问题放在后面说一下。
做以上操作是 \mathcal{O}(n) 的，至于求 w1,w2 使用双指针就可以了
所以应用主定理应该可以知道复杂度为 \mathcal{O}(n\log n) 的，相当优秀。
辰星凌老师在他的题解上说是因为前缀最大值或最小值有单调性，但是我认为，这就是普通的前缀和啊？不是很懂，如果错了能不能踢踢我，我也想知道
感谢大佬帮我解决了这个问题，这里给出解答：
双指针 的前提是有单调性，所以需要前缀最大值或最小值有单调性才可以双指针
最后是代码了，但是我觉得这道题应该不是很难调，所以我就不放了QWQ
错了踢踢我
完结撒花✿✿ヽ(°▽°)ノ✿