1 条题解

  • 0
    @ 2026-11-15 16:45:28

    题目分析

    琴(instrument)题解

    aia_i 最大只有 5050,容易想到对每次询问直接枚举值域。问题变成快速求出区间 [l,r][l,r] 中 xx 的出现次数,也就是 ∑i=lr[ai==x]\sum_{i=l}^r[a_i==x],对每个 xx 记 S(x,i)=∑j=1i[aj==x]S(x,i)=\sum_{j=1}^i [a_j==x],也就是每个值开一个前缀和数组,则出现次数为 S(x,r)−S(x,l−1)S(x,r)-S(x,l-1)。

    令 VV 为值域范围,我们先以 O(nV)O(nV) 的复杂度预处理出 SS 数组,对于每个询问从 11 枚举到 VV,先找到最小的出现在 [l,r][l,r] 里的数,再计算答案。复杂度 O((n+m)V)O((n+m)V)。

    • 1

    信息

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