前言
更重要的是研究这题的部分分, 赛时居然可以做到 \(1 \ \rm{h}\) 没有拿到任何一个特殊性质
发现以前一直用的大标题很碍眼, 改了, 下课把之前的格式也改一下
思路
暴力
容易模拟, 做到 \(25 \%\)
特殊性质 \(\rm{A}\)
思路
你发现每一个区间都是其后面区间的前缀, 而且每次长度只增加 \(1\)
容易注意到一个特殊性质区间答案单调递增
怎么处理
容易想到类似单指针的做法, 你维护已经有答案的区间前缀, 之后就是对于没有答案的区间的处理
问题在于如果修改到了已经有答案的区间前缀中, 会导致后面的答案出现问题, 如果要维护会导致复杂度出现问题
好吧仔细想一下容易发现, 你记录前缀中出现过的颜色, 然后一般的维护颜色的种类数, 然后你在扩展的时候处理即可
刚刚脑子糊了, 赛时脑子也糊了
没有按照正确顺序思考 + 脑子内存不足导致的
总结
注意这类区间不重问题的常见实现方式, 避免了更高复杂度的枚举
特殊性质 \(\rm{B}\)
思路
容易想到的是每次修改只修改包含他的区间, 问题出在怎么计算每个点被哪些区间包含, 以及如何维护每个区间的合法性?
计算每个点被哪些区间包含是简单的, 复杂度被限制在线性, 约束还是很强的
维护区间合法性显然不能使用上面的方法了, 空间开不下
不过你可以考虑根号分治, 对于 \(size \geq \sqrt{n}\) 的区间记录颜色, 否则直接枚举即可
容易证明这样子做的时空复杂度都符合要求
听了讲发现直接用 \(\rm{map}\) 搞能过, 考虑正确性证明:
考虑长度为 \(size\) 的区间中, 空间复杂度至多为 \(size\) , 至多有 \(\frac{n}{size}\) 个区间, 至多花费 \(\mathcal{O} (n)\) 的空间
考虑一共只有 \(n\) 个区间, \(size [k : n]\) 这样才能卡到上界, 即求
\[\sum_{i = n}^{k} \lfloor\frac{n}{k}\rfloor \leq n \]对应的最大 \(k\)
发现理论上是过不去的, 随机数据是这样的, 一会去问一下
好像别人不是这个意思, 不管了
哦哦哦, 听懂了, \(\rm{map}\) 没在这用
就当我上面这一坨都没说
总结
思路还是挺好想的, 难的是维护
灵机一动想到了根号分治, 本质上其实是空间复杂度跟个数有关, 时间复杂度跟长度有关联想到的经典应用
时空复杂度也可以用根分处理
特殊性质 \(\rm{C}\)
思路
可以发现一个区间如果在某一时刻区间内部颜色互不相同则之后永远内部颜色互不相同, 而且只要对于一个 \(size\) 的区间, 操作次数达到 \(size - 1\) 就可以保证其内部颜色不相同
怎么用?
考虑线段树维护区间修改次数以及区间最优时间以达到保证其内部颜色不相同
复杂度 \(\mathcal{O} (Q \log n)\)
总结
一类线段树的常见用法
正解
思路
看到包含和不相交其实很容易想到在图上处理
你发现直接丢到图上还不够, 包含关系是有传递性的, 可以搞成一棵树
发现建出树之后, 叶子结点区间之间无交集, 父亲节点一定比其儿子节点后满足要求, 特殊的, 不同树之间显然无交集
发现修改的一个点只会在一个区间之中, 于是我们先考虑怎么判断这个区间是否合法了
方法 \(1\)
发现相当于建出树之后进行单点修改, 子树数颜色, \(\rm{set}\) 搞一下即可, 也可以用 \(\rm{dfs}\) 序和值域树状数组
不研究了
方法 \(2\)
维护每个颜色在原序列上对应的链, 区间内部颜色互不相同就是这一位置上对应的颜色的链的上一位在区间外面
考虑维护, 直接维护 \(lst\) 表示链的上一位, 还是比较简单的
主要问题是对链的维护
然后就是怎么维护树
首先建树怎么建?
疑似可以用栈
其次怎么维护叶子结点?
疑似可以用 \(\rm{set}\) 存编号