问题一：数组元素的最小字典序映射

题意描述：给定一个包含 $n$ 个整数的数组，要求将数组中出现的每个数字映射到一个未在该数组中出现过的正整数。映射必须满足一一对应关系（即相同的原数字必须映射到相同的新数字，不同的原数字不能映射到相同的新数字）。目标是使得映射后输出的数组字典序最小。

算法解析：为了保证字典序最小，我们需要为原数组中出现的数字分配尽可能小的未出现正整数。可以使用哈希表（或布尔数组）记录原数组中已经出现的数字。遍历原数组时，维护一个指针指向当前可用的最小正整数。对于每个元素，如果它尚未被分配映射值，则不断递增指针，直到找到一个既不在原数组中、也未被分配过的数字，然后建立映射关系。

参考实现：

#include <iostream>
#include <vector>
#include <unordered_set>
#include <unordered_map>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    
    vector<int> a(n);
    unordered_set<int> present;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        present.insert(a[i]);
    }

    unordered_map<int, int> mapping;
    int next_available = 1;
    vector<int> result(n);

    for (int i = 0; i < n; ++i) {
        if (mapping.find(a[i]) == mapping.end()) {
            // 寻找下一个未被使用且不在原数组中的正整数
            while (present.count(next_available)) {
                next_available++;
            }
            mapping[a[i]] = next_available;
            present.insert(next_available); // 标记该数字已被使用
        }
        result[i] = mapping[a[i]];
    }

    for (int i = 0; i < n; ++i) {
        cout << result[i] << (i == n - 1 ? "" : " ");
    }
    cout << "\n";
    return 0;
}

问题二：学习资源的最大化分配

题意描述：共有 $m$ 个学习资源需要分配给 $n$ 个人。每个人至少需要 $k$ 个资源才能激活学习状态。激活后，每人学习 $t$ 分钟，每分钟获得 1 点收益，但单人收益上限为 $q$（即单人收益为 $\min(x \cdot t, q)$，其中 $x$ 为分配的资源数）。目标是合理分配这 $m$ 个资源，使得所有人的总收益最大化。

算法解析：这是一个典型的数学建模与贪心分配问题。设分配给某人的资源数为 $x$，其收益函数为 $f(x) = \min(x \cdot t, q)$ （当 $x \ge k$），否则为 0。由于 $f(x)$ 在 $x \ge k$ 时单调递增，且当 $x \ge \lceil q/t \rceil$ 时达到上限 $q$，最优策略是优先让尽可能多的人达到收益上限，剩余的资源再分配给下一个人（前提是满足 $k$ 的激活条件）。在实现时，必须使用 64 位整数（long long）以防止中间计算结果溢出。

参考实现：

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    long long n, m, k, q, t;
    if (!(cin >> n >> m >> k >> q >> t)) return 0;

    // 计算单人达到收益上限 q 所需的最小资源数
    long long limit = max(k, (q + t - 1) / t);
    
    long long max_profit = 0;
    
    // 策略1：优先让多人达到收益上限
    long long full_count = m / limit;
    long long remainder = m % limit;
    
    long long profit1 = full_count * q;
    if (remainder >= k) {
        profit1 += min(remainder * t, q);
    }
    max_profit = max(max_profit, profit1);
    
    // 策略2：将所有资源集中分配给一个人（边界情况处理）
    if (m >= k) {
        max_profit = max(max_profit, min(m * t, q));
    }

    cout << max_profit << "\n";
    return 0;
}

问题三：特定元素集合的合法子区间统计

题意描述：给定一个长度为 $n$ 的数组，元素仅包含 -2, -1, 1, 2。要求统计有多少个连续子区间，满足区间内最大值的绝对值等于最小值的绝对值（即 $|\max| = |\min|$）。

算法解析：由于元素集合的特殊性，合法区间可以分为三类互不重叠的情况： 1. 区间内所有元素的绝对值完全相同（如全为 1，或全为 -2）。 2. 区间内同时包含 1 和 -1，且不包含 2 和 -2。 3. 区间内同时包含 2 和 -2，且不包含 1 和 -1。 我们可以采用分块与容斥原理在 $O(N)$ 时间复杂度内解决。首先遍历数组，统计所有绝对值相同的连续段贡献的子区间数。接着，将绝对值为 2 的元素视为"障碍"，在由 1 和 -1 组成的连续段中，利用容斥原理（总子区间数 - 全为 1 的子区间数 - 全为 -1 的子区间数）计算同时包含 1 和 -1 的区间数。对 2 和 -2 的情况进行同理计算。

参考实现：

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

// 辅助函数：计算只包含 val1 和 val2 的连续段中，同时包含 val1 和 val2 的子区间数量
long long countMixedSubarrays(const vector<int>& a, int val1, int val2, int block1, int block2) {
    long long total = 0;
    int n = a.size();
    int i = 0;
    while (i < n) {
        if (abs(a[i]) != block1 && abs(a[i]) != block2) {
            i++;
            continue;
        }
        
        int j = i;
        long long len = 0;
        long long same1 = 0, same2 = 0;
        
        while (j < n && (abs(a[j]) == block1 || abs(a[j]) == block2)) {
            len++;
            j++;
        }
        
        long long curr_same = 0;
        for (int k = i; k < j; ++k) {
            if (a[k] == val1) {
                curr_same++;
            } else {
                same1 += curr_same * (curr_same + 1) / 2;
                curr_same = 0;
            }
        }
        same1 += curr_same * (curr_same + 1) / 2;
        
        curr_same = 0;
        for (int k = i; k < j; ++k) {
            if (a[k] == val2) {
                curr_same++;
            } else {
                same2 += curr_same * (curr_same + 1) / 2;
                curr_same = 0;
            }
        }
        same2 += curr_same * (curr_same + 1) / 2;
        
        total += len * (len + 1) / 2 - same1 - same2;
        i = j;
    }
    return total;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    long long ans = 0;

    // 1. 统计绝对值全相同的连续子区间
    int i = 0;
    while (i < n) {
        int j = i;
        while (j < n && abs(a[j]) == abs(a[i])) {
            j++;
        }
        long long len = j - i;
        ans += len * (len + 1) / 2;
        i = j;
    }

    // 2. 统计包含 1 和 -1，但不包含 2 和 -2 的子区间
    ans += countMixedSubarrays(a, 1, -1, 1, 1);

    // 3. 统计包含 2 和 -2，但不包含 1 和 -1 的子区间
    ans += countMixedSubarrays(a, 2, -2, 2, 2);

    cout << ans << "\n";
    return 0;
}