洛谷 T326569 统计区间内每个数出现次数的和 - 题解 - 常规

题目描述

给定一个长度为 $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$

输入样例

输出样例

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++ 代码

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5 + 5;

int n, m;
int a[MAXN], cnt[MAXN], sum[MAXN];

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
        ++cnt[a[i]];
        sum[i] = sum[i - 1] + cnt[a[i]];
    }
    for (int i = 1; i <= m; ++i) {
        int l, r;
        scanf("%d%d", &l, &r);
        int ans = sum[r] - sum[l - 1];
        for (int j = l; j <= r; ++j) {
            ans -= cnt[a[j]] * (j - l + 1);
        }
        printf("%d\n", ans);
    }
    return 0;
}

算法2

(线段树) $O(nlogn)$

时间复杂度

空间复杂度

C++ 代码