蓝桥杯 20. 压缩变换

压缩变换

原题目链接

题目描述

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

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

变换规则如下：

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

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

示例说明：

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

变换后序列为：-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]区间上有多少个不同的数，可以用线段树，或者树状数组，莫队算法。

线段树法

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