这是某场$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$.
对于后缀同理,从左向右递推即可.