自动搬运

查看原文

来自洛谷，原作者为

	Ajsoabk Ajsoooooooooooooabk

搬运于2025-08-24 21:59:28，当前版本为作者最后更新于2018-10-13 08:48:22，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这道题的关键是研究分隔点，元素与答案的关系

理解理解

定义分隔点i为元素i与i+1之间的一条分割线，简称点i

分清楚元素、位置、点的区别

问题转化：

1：对于一段已排完序的区间，每两个位置中间都有且仅有一个分隔点，换言之，区间有序的标志就是所有的分隔点都已出现

难道不是显然？

t[i]定义：

2：对于一个分隔点i，t[i]是它出现的时间

->是最后一个进来该区间的元素的时间

->是最右的本应在分隔点i左边的元素maxpos到点i的距离（最远的进来了，不就都进来了）

若没有这样的点则为1（出现时间最少是1）

这里的“本应在...（位置）”指的是最终位置，发现这个对3有启发，觉得表述不清的的下面有解释

答案转化

3：将答案ans的增加过程看成两个分隔点之间所有位置对ans产生1的贡献，一个位置会不断对答案产生贡献直到其左右两边都产生了分隔点（重要性质）

故由2，3可推出位置i对ans的贡献为max(t[i],t[i-1]),i：1~n，即位置i两边更晚出现的分隔点出现的时间

故ans是每个位置i的max(t[i],t[i-1])的和

小小的解释

最右的本应在分隔点i左边的元素maxpos到点i的距离

maxpos可用结构体在排序前将位置pos记录，排序后位置i及位置i之前pos的最大值即为maxpos

为何有些题解是max(t[i],t[i+1])

因为他们是从0~n-1 max(t[0],t[1])...max(t[n-1],t[n])不就是这里的 max(t[1],t[0])...max(t[n],t[n-1])