一类巧妙利用利用分治的序列求值

标签:这不   解决办法   需要   修改   line   最快   code   位置   重点   

I.PreFace

这个方法经常用于这类问题:

给定序列 \(A\),并定义基于序列 \(A\) 的函数 \(f(l, r)\),求 \(\sum\limits_{1 \leq i \leq j \leq n}f(l, r)\)

这个方法的核心做用是:

将不满足可减性的求值,变成只需要可以区间拼合(即满足区间可加性)的求值式子。

II.常用的解决办法:

  1. 拆成每个点的贡献处理。

  2. 从左到右推进端点 \(r\),开一个数据结构维护对于当前每个 \(l\) 的函数值 \(f(l,r)\),每推进一位 \(r\) 对应了一次的区间修改和一次的整体求和。

etc,这不是本文的重点。

III. 正文

考虑分治:

技术图片

这回我们只要求跨过中点的区间的贡献就够了,即求

\[\sum_{i=l}^{mid}\sum_{j=mid+1}^{r}f(i,j) \]

这个式子当然还是是 \(O(n^2)\) 的,但是常常它比原问题的那个更加的简便,有无穷的威力。简便在哪?简便在于,本来这个式子可能不满足区间可减性,但是经过这样的分治,它只需要区间可加就行了,于是可以转化为第 II 节中的方法。

设当前求解当前 \(mid\) 的时间复杂度为 \(O(f(r-l+1))\),那么总复杂度也就近似的可以认为是 \(O(f(n) \log n\)

IV. 随便的一道例题:

给定数列 \(A\),设 \(f(l,r)=\max\limits_{i=l}^{r}A_i\),求 \(\sum\limits_{i=1}^n\sum\limits_{j=i}^n f(i,j)\)

利用上述转化后问题就变成了可以用第 II 部分中的第一种处理,设 \(g(i)\) 为前缀/后缀最大值,那么它一定是单调的,即对于每一个位置的最大值的贡献,我就看一下另一边有多少个数小于它即可。尺取法一下复杂度 \(n\log n\)。事实上还有很多其他解法,这里只是作为一个 example。

V. 练习题:

GSOR 1008,谢谢出题人 lxl。

哈哈哈其实他给的做法都是 \(n \log^2 n\) 的,其实很轻松可以做到 \(n\log n\),于是就成了最短+最快解(哈哈哈!

一类巧妙利用利用分治的序列求值

标签:这不   解决办法   需要   修改   line   最快   code   位置   重点   

原文地址:https://www.cnblogs.com/Linshey/p/14165532.html

版权声明:完美者 发表于 2020-12-25 12:23:19。
转载请注明:一类巧妙利用利用分治的序列求值 | 完美导航

暂无评论

暂无评论...