蓝桥杯 20. 压缩变换

压缩变换

原题目链接

题目描述

小明最近在研究压缩算法。他知道，压缩时如果能够使数值很小，就能通过熵编码得到较高的压缩比。然而，要使数值变小是一个挑战。

最近，小明需要压缩一些正整数序列，这些序列的特点是：后面出现的数字，很可能是刚出现过不久的数字。为了压缩这些特殊序列，小明设计了一种变换规则，来减小数值大小。

---

变换规则如下：

从左到右枚举序列，对每个数字进行如下操作：

• 如果该数字没有出现过，将其变换为它的相反数；
• 如果该数字出现过，则找到它上一次出现的位置，计算从那次出现之后到当前位置之间出现了多少种不同的数字，并将这个种类数替换原来的数字。

---

示例说明：

给定序列 (1, 2, 2, 1, 2)，变换过程如下：

原序列位置	值	说明	变换后值
a₁	1	首次出现	-1
a₂	2	首次出现	-2
a₃	2	上次出现在 a₂，a₂ 到 a₃ 之间无新数字	0
a₄	1	上次出现在 a₁，a₁ 到 a₄ 之间有 1 个不同数字（2）	1
a₅	2	上次出现在 a₃，a₃ 到 a₅ 之间有 1 个不同数字（1）	1

变换后序列为：-1 -2 0 1 1

---

输入描述

• 第一行包含一个整数 n，表示序列的长度。
• 第二行包含 n 个正整数，表示原始序列。

数据范围：

• 1 ≤ n ≤ 10⁵
• 1 ≤ aᵢ ≤ 10⁹

---

输出描述

输出一行包含 n 个整数，表示变换后的序列，用空格分隔。

---

输入样例

5
1 2 2 1 2

---

输出样例

-1 -2 0 1 1

c++代码

#include<bits/stdc++.h>
#include<stdio.h>using namespace std;class query {
public:int l, r, key;
};int n, m;
vector<int> trees, arr;
vector<query> querys;
vector<vector<int>> end_by_r;
unordered_map<int, int> mp;
vector<string> temp;
unordered_map<string, int> ans;bool mycom(query a, query b) { return a.r < b.r; }void build(int p, int l, int r) {if (l == r) {trees[p] = 1;return;}int mid = (l + r) / 2;build(2 * p, l, mid);build(2 * p + 1, mid + 1, r);trees[p] = trees[2 * p] + trees[2 * p + 1];
}void update(int p, int l, int r, int k) {if (l == r && l == k) {trees[p] = 0;return;}int mid = (l + r) / 2;if (k <= mid) update(2 * p, l, mid, k);else update(2 * p + 1, mid + 1, r, k);trees[p] = trees[2 * p] + trees[2 * p + 1];
}int ask(int p, int l, int r, int range_l, int range_r) {if (range_l <= l && range_r >= r) return trees[p];int mid = (l + r) / 2, ans = 0;if (mid >= range_l) ans += ask(2 * p, l, mid, range_l, range_r);if (mid < range_r) ans += ask(2 * p + 1, mid + 1, r, range_l, range_r);return ans;
}int main() {scanf("%d", &n);trees = vector<int>(4 * n), arr = vector<int>(n + 1), end_by_r = vector<vector<int>>(n + 1);for (int i = 1; i <= n; i++) scanf("%d", &arr[i]);build(1, 1, n);for (int i = 1; i <= n; i++) {if (mp.find(arr[i]) != mp.end()) {int x = mp[arr[i]], y = i;x++, y--;if (x <= y) {query q;q.l = x, q.r = y, q.key = querys.size();querys.push_back(q);}}mp[arr[i]] = i;}mp.clear();m = querys.size();sort(querys.begin(), querys.end(), mycom);for (int i = 0; i < m; i++) end_by_r[querys[i].r].push_back(i);for (int i = 1; i <= n; i++) {if (mp.find(arr[i]) != mp.end()) update(1, 1, n, mp[arr[i]]);mp[arr[i]] = i;for (int x : end_by_r[i]) {string s = to_string(querys[x].l) + " " + to_string(querys[x].r);ans[s] = ask(1, 1, n, querys[x].l, querys[x].r);}}mp.clear();for (int i = 1; i <= n; i++) {if (mp.find(arr[i]) == mp.end()) {mp[arr[i]] = i;arr[i] = -arr[i];}else {int x = mp[arr[i]], y = i;mp[arr[i]] = i;x++, y--;if (x > y) arr[i] = 0;else arr[i] = ans[to_string(x) + " " + to_string(y)];}}for (int i = 1; i <= n; i++) {printf("%d", arr[i]);if (i != n) printf(" ");}return 0;
}//by wqs

题目解析

我们需要设计一个算法快速求出[L,R]区间上有多少个不同的数，可以用线段树，或者树状数组，莫队算法。

线段树法

然后就是套模版进去就行。