Nén số

Simple compression
Deep compresssion
- Bài tập ứng dụng

Kĩ thuật nén số, còn được gọi là kĩ thuật rời rạc hóa, kĩ thuật này sẽ giảm giá trị các số lại giúp tiết kiệm bộ nhớ, tăng tốc độ thực thi, … Một trong những hệ quả quan trọng của kĩ thuật này là các giá trị sau khi nén vẫn giữ nguyên quan hệ so sánh của các giá trị tương ứng trước khi nén (vd: \(a\) nén thành \(a'\), \(b\) nén thành \(b'\) ta có hệ quả \(a = b \Leftrightarrow a' = b'\), \(a < b \Leftrightarrow a' < b'\), …).

Simple compression

Đây là cách nén cơ bản thường dùng, các số sau khi nén sẽ giữ nguyên quan hệ so sánh của các số tương ứng trước khi nén.

Cách 1: \(O(Nlog(N))\)

int compress(vector<int>&v) {
    vector<int> tmp = v;
    sort(tmp.begin(),tmp.end());
    tmp.erase(unique(tmp.begin(),tmp.end()),tmp.end());
    for (int i = 0; i < v.size(); ++i) {
        v[i] = lower_bound(tmp.begin(),tmp.end(),v[i]) - tmp.begin();
    }
    return (int)tmp.size()-1; // return max value
}

Cách 2: \(O(Nlog(N))\)

int compress(vector<int>&v) {
    int *tmp[v.size()];
    for (int i = 0; i < v.size(); ++i) {
        tmp[i] = &v[i];
    }
    sort(tmp,tmp+v.size(),[&](int*x,int*y) {
        return *x < *y;
    });
    int num = 0; // min value
    int last = *tmp[0]; // last compressed value
    *tmp[0] = num;
    for (int i = 1; i < v.size(); ++i) {
        if (last != *tmp[i]) {
            num++;
            last = *tmp[i];
        }
        *tmp[i] = num;
    }
    return num; // return max value
}

Nhận xét: Cách nén này giúp độ chênh lệch giữa giá trị lớn nhất và nhỏ nhất không vượt quá là số lượng phần tử, mặc dù cả hai cách trên đều có độ phức tạp là \(O(Nlog(N))\) nhưng cách nén thứ hai vì chỉ có sort là \(O(Nlog(N))\) còn lại là duyệt \(O(N)\) nên nhanh hơn cách thứ nhất.

Bài tập ứng dụng

http://online.vku.udn.vn/problem/joyful

solution

// link de: http://online.vku.udn.vn/problem/joyful

#include <bits/stdc++.h>
#define fi first
#define se second
#define debug(x) cerr << #x << " = " << x << '\n'

using namespace std;

struct Point {
    int x, y;
    friend istream& operator >> (istream&is,Point&p) {
        is >> p.x >> p.y;
        return is;
    }
};

struct Segment {
    Point a, b;
    friend istream& operator >> (istream&is,Segment&s) {
        is >> s.a >> s.b;
        if (s.a.x > s.b.x) swap(s.a.x,s.b.x);
        if (s.a.y > s.b.y) swap(s.a.y,s.b.y);
        return is;
    }
    bool isHor() {
        return a.y == b.y;
    }
};

struct item {
    int x, y, z;
    bool operator < (item&i) {
        return x < i.x;
    }
};

const int N = 2e5+7;
int n;
Segment s[N];
int *B[2*N], maxY, val;

namespace sub2 {
    item hor[N*2], ver[N];
    int shor = 0, sver = 0;
    struct BIT {
        int n;
        int f[2*N], a[2*N];
        void init(int n_) {
            n = n_;
        }
        void update(int i, int k) {
            for (int j = i; j <= n; j+=j&-j) {
                f[j] += k;
            }
            a[i] += k;
        }
        int sum(int x, int y) {
            int res = 0;
            while (y >= x) {
                if (y-(y&-y)+1 >= x) {
                    res += f[y];
                    y -= y&-y;
                }
                else { res += a[y--]; }
            } return res;
        }
    } f;

    long long solve() {
        long long res = 0;
        for (int i = 0; i < n; ++i) {
            if (s[i].isHor()) {
                hor[shor++] = {s[i].a.x,s[i].a.y,1};
                hor[shor++] = {s[i].b.x+1,s[i].b.y,-1};
            }
            else {
                ver[sver++] = {s[i].a.x,s[i].a.y,s[i].b.y};
            }
        }
        sort(hor,hor+shor);
        sort(ver,ver+sver);
        f.init(maxY);
        int j = 0;
        while (j < sver && ver[j].x < hor[0].x) j++;
        for (int i=0; i < shor; ++i) {
            f.update(hor[i].y,hor[i].z);
            if (i+1 == shor) break;
            if (hor[i].x != hor[i+1].x) {
                while (j < sver && ver[j].x < hor[i+1].x) {
                    res += f.sum(ver[j].y,ver[j].z);
                    j++;
                }
            }
            if (j == sver) break;
        }
        return res;
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> s[i];
    }
    for (int i = 0; i < n; ++i) {
        B[i] = &s[i].a.y;
        B[i+n] = &s[i].b.y;
    }
    sort(B,B+2*n,[&](int *a, int *b) {
        return *a < *b;
    });
    for (int i = 0; i < 2*n; ++i) {
        if (i == 0 || *B[i] != val) { maxY++; val = *B[i]; }
        *B[i] = maxY;
    }
    cout << sub2::solve();
    return 0;
}

https://cses.fi/problemset/task/1734

solution

#include <bits/stdc++.h>

using namespace std;

int block;
struct Query {
   int l, r, idx;
   pair<int,int> toPair() const {
       return make_pair(l/block, l/block & 1 ? -r : r);
   }
};

const int N = 2e5+7;
int n, q, a[N];
vector<Query> que;
int cnt[N], res, ans[N];

void compress() {
   int *tmp[n];
   for (int i = 1; i <= n; ++i) tmp[i-1] = &a[i];
   sort(tmp,tmp+n,[&](int*x,int*y) { return *x < *y; });
   for (int i = 0, num = 0, last; i < n; ++i) {
       if (i==0 || last != *tmp[i]) {
           num++; last = *tmp[i];
       } *tmp[i] = num;
   }
}

int main() {
   cin.tie(nullptr)->sync_with_stdio(false);
   cin >> n >> q;
   for (int i = 1; i <= n; ++i) cin >> a[i];
   for (int i = 0; i < q; ++i) {
       int l, r; cin >> l >> r;
       que.push_back({l,r,i});
   }
   compress();
   block = sqrt(n);
   sort(que.begin(),que.end(),[&](const Query& a, const Query& b) {
       return a.toPair() < b.toPair();
   });
   int l = 1, r = 0;
   for (int i = 0; i < q; ++i) {
       for (; l < que[i].l; res-=--cnt[a[l]]==0, ++l);
       for (; l > que[i].l; --l, res+=++cnt[a[l]]==1);
       for (; r > que[i].r; res-=--cnt[a[r]]==0, --r);
       for (; r < que[i].r; ++r, res+=++cnt[a[r]]==1);
       ans[que[i].idx] = res;
   }
   for (int i = 0; i < q; ++i) cout << ans[i] << '\n';
   return 0;
}

https://cses.fi/problemset/task/1144

solution

#include <bits/stdc++.h>
 
using namespace std;
 
struct Query {
    char k;
    int x, y;
};
 
int n, q;
vector<int> a;
vector<int*> tmp;
vector<Query> que;
 
struct BIT {
    int size;
    vector<int> f, a;
    void init(int n) {
        size = n;
        f.assign(size+1,0);
        a.assign(size+1,0);
    }
    void add(int i, int k) {
        a[i] += k;
        for (int j = i; j <= size; j+=j&-j) {
            f[j] += k;
        }
    }
    int num(int x, int y) {
        int s = 0;
        while (y>=x) {
            if (y-(y&-y)+1 >= x) {
                s += f[y];
                y -= y&-y;
            } 
            else {
                s += a[y];
                y--;
            }
        } return s;
    }
} f;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> q;
    a.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        tmp.push_back(&a[i]);
    }
    for (int i = 0; i < q; ++i) {
        char k;
        int x, y;
        cin >> k >> x >> y;
        que.push_back({k,x,y});
    }
    for (int i = 0; i < q; ++i) {
        if (que[i].k=='?') tmp.push_back(&que[i].x);
        tmp.push_back(&que[i].y);
    }
    sort(tmp.begin(),tmp.end(),[&](int*a,int*b) {
        return *a < *b;
    });
    int num = 0;
    for (int i=0,last=-1; i < tmp.size(); ++i) {
        if (i==0 || *tmp[i] != last) {
            last = *tmp[i];
            num++;
        }
        *tmp[i] = num;
    }
    f.init(num);
    for (int i : a) f.add(i,1);
    for (auto& q : que) {
        if (q.k == '!') {
            f.add(a[q.x-1],-1);
            f.add(q.y,1);
            a[q.x-1]=q.y;
        }
        else cout << f.num(q.x,q.y) << '\n';
    }
    return 0;
}

Deep compression

Cách nén này nghiêm ngặt hơn cách trên, ngoài giữ nguyên quan hệ so sánh, cách này còn đảm bảo các các cặp số liền kề sau khi nén vẫn liền kề (cách trên vẫn thỏa tính chất này), và các cặp số không liền kề sau khi nén cũng không liền kề

int deepCompress(vector<int>&v) {
    int *tmp[v.size()];
    for (int i = 0; i < v.size(); ++i) {
        tmp[i] = &v[i];
    }
    sort(tmp,tmp+v.size(),[&](int*x,int*y) {
        return *x < *y;
    });
    int num = 0; // min value
    int last = *tmp[0]; // last compressed value
    *tmp[0] = num;
    for (int i = 1; i < v.size(); ++i) {
        if (last != *tmp[i]) {
            num += 1 + (*tmp[i]-last>1);
            last = *tmp[i];
        }
        *tmp[i] = num;
    }
    return num; // return max value
}

Nhận xét: Cách nén này thường dùng để nén các giá trị liên quan đến vị trí như tọa độ đoạn thẳng, điểm, …

Lưu ý: Vì phải thỏa mãn thêm tính chất liền kề nên chênh lệch giữa giá trị lớn nhất và nhỏ nhất không vượt quá 2 lần số lượng phần tử.

Bài tập vận dụng

https://oj.vnoi.info/problem/fct023_segment

solution

#include <bits/stdc++.h>

using namespace std;

const int MAX = 16e5+7;
const int LOG = 21;
const int N = 2e5+7;
int numSeg, numQue, numNode;
pair<int,int> segs[N], ques[N];
vector<int> adj[MAX];
int anc[MAX][LOG];

void dfs(int u) {
    for (int i = 1; i < LOG; ++i) {
        anc[u][i] = anc[anc[u][i-1]][i-1];
    }
    for (int v : adj[u]) {
        anc[v][0] = u;
        dfs(v);
    }
}

int compress() {
    int tmpSize = 0;
    int* tmp[numSeg*2 + numQue*2];
    for (int i = 0; i < numSeg; ++i) {
        tmp[tmpSize++] = &segs[i].first;
        tmp[tmpSize++] = &segs[i].second;
    }
    for (int i = 0; i < numQue; ++i) {
        tmp[tmpSize++] = &ques[i].first;
        tmp[tmpSize++] = &ques[i].second;
    }
    sort(tmp,tmp+tmpSize,[&](int*x, int*y) {
        return *x < *y;
    });
    int num = 2;
    int last = *tmp[0];
    *tmp[0] = num;
    for (int i = 1; i < tmpSize; ++i) {
        if (i==0 || last != *tmp[i]) {
            num += 1 + (*tmp[i]-last > 1);
            last = *tmp[i];
        }
        *tmp[i] = num;
    }
    return num;
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> numSeg;
    for (int i = 0; i < numSeg; ++i) {
        cin >> segs[i].first >> segs[i].second;
    }   
    cin >> numQue;
    for (int i = 0; i < numQue; ++i) {
        cin >> ques[i].first >> ques[i].second;
    }
    numNode = compress() + 1;
    sort(segs,segs+numSeg);
    for (int i = 2, j = 0, mx = -1; i <= numNode; ++i) {
        while (j < numSeg && segs[j].first <= i) {
            mx = max(mx, segs[j].second);
            j++;
        }
        int x = mx < i ? 1 : mx+1;
        adj[x].push_back(i);
    }
    dfs(1);
    for (int i = 0; i < numQue; ++i) {
        int lef = ques[i].first;
        int rig = ques[i].second;
        int cnt = 0;
        for (int j = LOG-1; j >= 0; --j) {
            if (1 < anc[lef][j] && anc[lef][j] < rig+1) {
                cnt |= 1<<j;
                lef = anc[lef][j];
            }
        }
        if (anc[lef][0] > rig) {
            cout << cnt+1 << '\n';
        }
        else {
            cout << -1 << '\n';
        }
    }
}