木棍的长度

💐The Begin💐点点关注，收藏不迷路💐

在一个架子上从左至右依次摆放了n根小木棍，每根木棍都有一个长度，其中可能有多根长度相同的木棍。现在有Q次查询，对于每一个给定的查询，给你两个整数L和R，你需要求出编号L到编号R之间有不同长度的棍子的长度之和。木棍的编号从左到右分别对应从1到n。

输入

第一行输入一个整数T（T <= 10），表示有T组测试数据。

接下来一行输入一个整数n（n <= 20000）。

接下来一行输入n个正整数，分别表示n根木棍的长度length（0 <= length <= 1e8）。

接下来一行输入一个整数Q（Q <= 100000），表示有Q次查询。

接下来Q行，每行包含两个整数L和R（1 <= L <= R <= n）。

输出

输出每次查询的不同长度的木棍的长度之和在单独的一行。

样例输入

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

样例输出

2
13

#include <iostream>
#include <unordered_map>
using namespace std;

const int MAX_N = 20000;     // 根据题目中n的最大值定义一个合适的常数
const int MAX_LENGTH = 1e8;     // 根据题目中长度范围定义一个合适的常数

int main() {
    int t;
    cin >> t;     // 读取测试数据组数
    while (t–) {
        int n;
        cin >> n;         // 读取木棍数量
        int lengths[MAX_N];
        for (int i = 0; i < n; i++) {
            cin >> lengths[i];             // 读取每根木棍的长度
        }
        // 用普通数组记录每个位置之前不同长度的木棍长度之和
        int preSum[MAX_N + 1] = {0};
        // 用哈希表记录每个长度出现的次数，辅助计算前缀和
        unordered_map<int, int> lengthCount;
        for (int i = 0; i < n; i++) {
            preSum[i + 1] = preSum[i];
            int curLength = lengths[i];
            // 如果当前长度之前没出现过（出现次数为0），将其加入总和
            if (lengthCount[curLength] == 0) {
                preSum[i + 1] += curLength;
            }
            lengthCount[curLength]++;
        }
        int q;
        cin >> q;         // 读取查询次数
        while (q–) {
            int l, r;
            cin >> l >> r;             // 读取每次查询的左右区间
            l–;             // 转换为下标从0开始
            r–;
            // 用于临时记录区间内不同长度及其出现次数，避免重复计算总和
            unordered_map<int, int> tempCount;
            int sum = 0;
            for (int i = l; i <= r; i++) {
                int curLength = lengths[i];
                // 如果当前长度在区间内第一次出现，才加入总和
                if (tempCount[curLength] == 0) {
                    sum += curLength;
                }
                tempCount[curLength]++;
            }
            cout << sum << endl;
        }
    }
    return 0;
}

💐The End💐点点关注，收藏不迷路💐