3 条题解

  • 0
    @ 2023-3-11 20:11:06

    首先这个题离线直接莫队即可。

    然后还有另一种做法。

    就是二分答案 xx,然后数有多少种颜色没有在区间内出现过,即统计 (i,nxt[i])(i, nxt[i])[1,l1][r+1,n][1, l - 1][r + 1, n] 内的个数,整体二分即可。

    在线怎么搞。

    莫队寄了。

    然后那个二分答案的话要在线三维偏序,空间应该是2log的(如果有1log做法请指正。

    出题人写的是值域分块。

    s[i][j][k]s[i][j][k] 表示第 ii 块到第 jj 块内值域第 kk 块出现的颜色数,记 app[i][j]app[i][j] 表示前 ii 块内 jj 出现的次数。

    我们要知道什么?我们要知道值域第 kk 块在 [l,r][l, r] 区间内出现了几个,以及 xx 这个颜色有没有在 [l,r][l, r] 内出现。

    后者是容易的,而前者呢。

    我们用零散块内的元素去更新整块区间的 ss

    具体地,设整块区间为第 ll 块到第 rr 块,开一个 cntcnt 数组,若当前元素 xxcnt[x]=0cnt[x] = 0 且在 [l,r][l, r] 这几个整块内没有出现过,那就更新 s[l][r][belong[x]]s[l][r][belong[x]],然后给 cnt[x]cnt[x] 加一。

    查询时找到第 kk 小所在的块然后枚举即可。

    信息

    ID
    277
    时间
    3000ms
    内存
    512MiB
    难度
    8
    标签
    (无)
    递交数
    29
    已通过
    6
    上传者