CF1285F Good Subsegments

发表于 2025-03-07 分类于算法竞赛，题， Codeforces 阅读次数：

题意：给出长度为的一个排列。

定义一个集合是连续的，当且仅当

次询问某个区间有多少个子区间是连续的。

允许离线。，时限。

子问题: CF526F Pudding Monstershttps://www.luogu.com.cn/problem/CF526F)

序列扫描线。枚举右端点，对于每个左端点维护区间的答案。当向右移动时，会在每个区间右侧加入。考虑其影响。

使用单调栈，可以使用若干次区间加法完成对和的维护。

但是，统计满足的区间的个数并不容易。又可以证明，所以只需要把位置的初始值设为，然后维护最小值以及最小值个数即可。

本题

把区间视为平面直角坐标系上的点。连续区间的贡献为，不连续区间的贡献为。题目要求区间的连续子区间个数，即如图红色部分的贡献之和，即蓝色部分贡献的历史版本和。

注意更新标记只能传给最小值相等的儿子。