P6406 [COCI2014-2015#2] Norma
艹
曰，口土 了。
十
\[\sum_{i=1}^N\sum_{j=i}^N(j-i+1) \cdot \min_{p=i}^j\{a_p\} \cdot \max_{q=i}^{j}\{a_q\}
\]
亚
心 式子。
反正我也想不出来分治，得题解而借鉴之。
在分治的时候，\([l, mid]\) 和 \([mid+1, r]\) 可以递归得到，那么考虑跨过 \(mid\) 的答案。
记录左边部分的最小值为 \(minn\)， 最大值为 \(maxn\)。
考虑 \(p, q\)
- 使得 \(val_{p}\) 恰好小于等于 \(minn\) 且 \(val_{p-1}\) 大于 \(minn\)。
- 使得 \(val_{q}\) 恰好大于等于 \(maxn\) 且 \(val_{q-1}\) 小于 \(maxn\)。
那么拆开算呗。
现在假定 \(p \lt q\)
- 对于区间 \([mid+1, p-1]\) 你就有 \(minn \cdot maxn \cdot \sum_{j = mid + 1}^{p - 1} (j - i + 1)\)。
- 对于区间 \([p, q-1]\) 你就有 \(maxn \cdot \sum_{j=p}^{q-1}(min[j] \cdot (j-i+1)) = maxn \cdot \sum_{j=p}^{q-1}(min[j] \cdot j - min[j] \cdot i + min[j])\)。
- 对于区间 \([q, r]\) 你就有 \(\sum_{j=q}^{r}(min[j] \cdot max[j] \cdot (j-i+1)) = \sum_{j=q}^r (min[j] \cdot max[j] \cdot j - min[j] \cdot max[j] \cdot i + min[j] \cdot max[j])\)。
现在假定 \(p \ge q\)
- 对于区间 \([mid+1, q-1]\) 你就有 \(minn \cdot maxn \cdot \sum_{j = mid + 1}^{q - 1} (j - i + 1)\)。
- 对于区间 \([q, p-1]\) 你就有 \(minn \cdot \sum_{j=q}^{p-1}(max[j] \cdot (j-i+1)) = minn \cdot \sum_{j=q}^{p-1}(max[j] \cdot j - max[j] \cdot i + max[j])\)。
- 对于区间 \([p, r]\) 你就有 \(\sum_{j=p}^{r}(min[j] \cdot max[j] \cdot (j-i+1)) = \sum_{j=p}^r (min[j] \cdot max[j] \cdot j - min[j] \cdot max[j] \cdot i + min[j] \cdot max[j])\)。
然后你就知道需要维护 \(min[j], max[j],min[j] \cdot j, max[j] \cdot j, min[j] \cdot max[j], min[j] \cdot max[j] \cdot j\) 的前缀和。
然后馒馒抄式子。
/*
Name:
Author: Gensokyo_Alice
Date:
Description:
*/
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include