琴(instrument)题解
aia_iai 最大只有 505050,容易想到对每次询问直接枚举值域。问题变成快速求出区间 [l,r][l,r][l,r] 中 xxx 的出现次数,也就是 ∑i=lr[ai==x]\sum_{i=l}^r[a_i==x]∑i=lr[ai==x],对每个 xxx 记 S(x,i)=∑j=1i[aj==x]S(x,i)=\sum_{j=1}^i [a_j==x]S(x,i)=∑j=1i[aj==x],也就是每个值开一个前缀和数组,则出现次数为 S(x,r)−S(x,l−1)S(x,r)-S(x,l-1)S(x,r)−S(x,l−1)。
令 VVV 为值域范围,我们先以 O(nV)O(nV)O(nV) 的复杂度预处理出 SSS 数组,对于每个询问从 111 枚举到 VVV,先找到最小的出现在 [l,r][l,r][l,r] 里的数,再计算答案。复杂度 O((n+m)V)O((n+m)V)O((n+m)V)。
使用您的 Hydro 通用账户