P3124 看错题

· · 个人记录

一开始以为可以增大两堆干草，其实这样也能做。

奶牛的右边一定有一个干草作为限制，所以先枚举右边的干草

然后可以用线段树来维护左边的干草的贡献最小值，能使左边干草有贡献的右干草一定是一段后缀，所以把左干草放在第一个使它有贡献的右干草处，枚到这个点了就加入算贡献就行了。

右干草的贡献也很好统计，考虑到能对右干草产生贡献的左干草一定是一段前缀，所以在线段树上查询时找到那个分界点分两段查询就行了。

复杂度 n\log n，感觉不是很好写。