httpswwwluogucomcnproblemT326569contestId=104457

题目描述

给定一个长度为 $n$ 的整数序列 $a_1,a_2,\cdots,a_n$。再给定 $m$ 个询问，每个询问给出 $l,r$，求区间 $[l,r]$ 中每个数在序列中出现次数的和。

输入格式

第一行两个整数 $n,m$。

第二行包含 $n$ 个整数 $a_1,a_2,\cdots,a_n$。

接下来 $m$ 行，每行两个整数 $l,r$。

输出格式

输出共 $m$ 行，每行一个整数表示对应询问的结果。

数据范围

$1\le n,m\le 10^5,-10^9\le a_i\le 10^9$

输入样例

5 3 1 2 1 3 4 1 5 2 4 3 5

输出样例

11 5 8

算法1

(离线算法) $O(nlogn)$

令 $cnt_{i}$ 表示 $a_i$ 的出现次数，$sum_{i}$ 表示 $[1,i]$ 中所有数出现次数的和。

对于每个询问 $[l,r]$，答案即为 $sum_r-sum_{l-1}-\sum_{i=l}^rcnt_i\cdot (i-l+1)$，其中 $sum_r-sum_{l-1}$ 表示区间 $[l,r]$ 中所有数出现次数的和，$\sum_{i=l}^rcnt_i\cdot (i-l+1)$ 表示区间 $[l,r]$ 中重复计算的部分。

时间复杂度

预处理 $cnt$ 和 $sum$ 的时间复杂度为 $O(n)$，对于每个询问需要计算 $O(1)$ 的答案，故总时间复杂度为 $O(n+m)$。

空间复杂度

需要 $O(n)$ 的额外空间存储 $cnt$ 和 $sum$ 数组。

C++ 代码

算法2

(线段树) $O(nlogn)$

时间复杂度

空间复杂度

C++ 代码