这是某场(CF(DIv.1+Div2))的题目的数据弱化版,不需要离散化直接(map)就可以过.
我当时直接选择了(Ctrl+C)然后(Ctrl+V),所以在比赛开始(2:55)的时候就(AC)了.
这道题的(O(n^2 log_2 n))直接参见我之前写的博客吧:这里
然鹅这题有更加优秀的(O(n))或者(O(n log_2 n))做法.
答案序列一定是一段前缀和一段后缀拼凑起来的.然后你考虑维护每个数字向右的相同数字的位置.
假如说,你要删除的区间是([a,b]),那么前缀里相同数字的下标的(min)一定要大于等于(a),而(max)一定要小于等于(b).
对于后缀同理,从左向右递推即可.