1 条题解

  • 0
    @ 2026-11-15 13:51:53

    题目分析

    20 分

    暴力搜索并比较字典序即可。

    40 分

    显然最长的子序列的长度就是数字种类数。

    有一个非常显然的暴力,看选择了一个数后能否取到答案的最大值,如果能取到说明这个数可以选,否则不行,每次在能选的数里面选最大/最小的那一个,暴力实现的话是 O(n3)\mathcal{O}(n^3)。

    80 分

    考虑优化上述暴力,注意到 check 一个数能不能选就是看一个后缀的数字种类数,这个是容易维护的,可以做到 O(n2)\mathcal{O}(n^2)。

    正解

    注意到取到答案的最大值的位置组成了一个前缀。

    设 edxed_x 表示 xx 出现的最后一个位置,那么 1∼min⁡x∈Sedx1\sim \min_{x\in S}ed_x 这个前缀都能取到最大值,这是显然的。

    那么就好做了,用 setset 维护 edxed_x 组成的集合,每次取出最小的一个,每次会询问一个区间 [l,r][l,r] 的最小或最大值,因为左右端点右移,可以利用单调队列优化。

    • 1

    信息

    ID
    74
    时间
    1000ms
    内存
    256MiB
    难度
    5
    标签
    递交数
    1
    已通过
    1
    上传者