壓縮變換
原題目鏈接
題目描述
小明最近在研究壓縮算法。他知道，壓縮時如果能夠使數值很小，就能通過熵編碼得到較高的壓縮比。然而，要使數值變小是一個挑戰。
最近，小明需要壓縮一些正整數序列，這些序列的特點是：后面出現的數字，很可能是剛出現過不久的數字。為了壓縮這些特殊序列，小明設計了一種變換規則，來減小數值大小。
變換規則如下：
從左到右枚舉序列，對每個數字進行如下操作：
- 如果該數字沒有出現過，將其變換為它的相反數；
- 如果該數字出現過，則找到它上一次出現的位置，計算從那次出現之后到當前位置之間出現了多少種不同的數字，并將這個種類數替換原來的數字。
示例說明：
給定序列 (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]區間上有多少個不同的數，可以用線段樹，或者樹狀數組，莫隊算法。
線段樹法
然后就是套模版進去就行。
)
