CF1209G2 Solution
根据题意,对于一个颜色的所有下标集合 \(S\),设其最小,最大位置是 \(l,r\),那么最后染完色的 \([l,r]\) 区间一定是同一种颜色。
如果有两个颜色 \(i,j\),\([l_i,r_i]\) 和 \([l_j,r_j]\) 有交集,那么这个区间并起来的大区间也一定是同一种颜色的。
这样我们并并并可以得到一些互不相交,且覆盖了 \([1,n]\) 的区间。设对于一种颜色 \(i\),其集合大小为 \(s_i\)。
对于每个区间,把区间内数都变成一样的操作代价显然是 \(r-l-mxs\),\(mxs\) 是区间内原来颜色的 \(s\) 的最大值。
下面是妙妙转化。对于每个颜色 \(i\),设一个数组 \(b\)。我们把 \([l_i,r_i)\) 的 \(b\) 加 \(1\)。那么每个 \(b_i=0\) 的位置就是大区间的末尾。
再来一个数组 \(c\),把每种颜色的下标数量放在 \(c_l\)。现在要求的就是,按照 \(b\) 的 \(0\) 分段后每段的 \(c\) 最大值之和。
还要支持 \(b\) 的区间加减、\(c\) 的单点修改。这些可以用线段树维护。
具体地,维护每个区间的最大值,从左端点向右/右端点向左一段的最大值,以及区间的答案,push_up
容易实现。
复杂度 \(O(n\log n)\)。
标签:颜色,最大值,solution,mxs,cf1209g2,区间 From: https://www.cnblogs.com/iorit/p/18038177