题目

有一个数列,长度为 $n$ 。有 $q$ 个询问,每次询问所有长度为 $k$ 的区间的最大值之和。
$q\leq 1e6$ ,$n\leq 1e6$,$k\in [1,n]$ 。

题解

先拆一波贡献,把答案转化为每一个数对与每一个询问的贡献。
可以发现,一个数对一个询问有贡献 (即被当做最大值取到),当且仅当这个区间包括它,但不包括它前面第一个比它大的那个数和他后面第一个比他大的数。
它前面第一个比它大的那个数和他后面第一个比他大的数可以单调栈 $\Theta (n)$。
然后对询问建线段树,考虑序列中的一个数,它和它前面第一个比它大的那个数的下标之差 (也就是距离) 为 $x$,它和它后面第一个比它大的那个数的下标之差为 $y$ ,不妨令 $x\leq y$。
那么,这个数字对于 $1$到 $n$询问的贡献可以分为三段:
$1.\ k\in (0,x]$ :贡献为 $k$。
$2.\ k\in (x,y]$ :贡献为 $x$。
$3.\ k\in (y,n]$ :贡献为 $x+y-k$。(可能具体边界上还有需要修正的地方,但大概就是这个意思)
那么,我们可以发现,第一段和第三段是区间加等差数列,第二段是区间加,这都可以用线段树来很好的维护。
复杂度 $\Theta (nlog_{2}n)$。

感谢 $Qiuly$ 帮补了一些 $\LaTeX$ 。

分类: 文章

darken

2018级退役OIer,QQ:2578050796。 博客园:https://www.cnblogs.com/thedreammaker/ 有问题请QQ联系,个人原因应该不会经常上OI相关网站了,不过如果有OI问题的话也可以来问我,但答不答的出来就说不准了QAQ

2 条评论

Remmina · 2020年4月1日 10:30 下午

QwQ 看我光速审核 23333

    darken · 2020年4月1日 10:31 下午

    真·光速审核 (滑稽)

发表评论

电子邮件地址不会被公开。 必填项已用*标注