1 条题解
-
0
题目分析
20 分
暴力搜索并比较字典序即可。
40 分
显然最长的子序列的长度就是数字种类数。
有一个非常显然的暴力,看选择了一个数后能否取到答案的最大值,如果能取到说明这个数可以选,否则不行,每次在能选的数里面选最大/最小的那一个,暴力实现的话是 。
80 分
考虑优化上述暴力,注意到 check 一个数能不能选就是看一个后缀的数字种类数,这个是容易维护的,可以做到 。
正解
注意到取到答案的最大值的位置组成了一个前缀。
设 表示 出现的最后一个位置,那么 这个前缀都能取到最大值,这是显然的。
那么就好做了,用 维护 组成的集合,每次取出最小的一个,每次会询问一个区间 的最小或最大值,因为左右端点右移,可以利用单调队列优化。
- 1
信息
- ID
- 74
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 5
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者