P4372 [USACO18OPEN]Out of Sorts P
这道题的关键是研究分隔点，元素与答案的关系
理解理解
定义分隔点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])