Coordinate Compression

Coordinate compression replaces known values by dense ranks while preserving equality and relative ordering. An array may contain coordinates near 10^12 but only a few distinct values; ranks 0..d−1 let frequency arrays, Fenwick trees and segment trees operate on those observed keys. Compression is a representation change, not a claim that original numeric distances or arithmetic are preserved.

Prerequisites: Sorting; binary search; frequency arrays.

Build the idea

1. 1. Build an ordered dictionary

   Copy original values into keys, sort them and remove duplicates. For [100,−5,100,7], keys becomes [−5,7,100]. Each dictionary position is the rank of its value. Keep original separately so output ranks still follow the input order. Sorting the original in place without saving positions loses that relationship.

2. 2. Understand unique and erase

   std::unique moves one copy of each consecutive distinct value into a prefix and returns its new end. It does NOT resize the vector. The erase(newEnd,end) step removes the unwanted suffix. Sorting first makes all duplicates consecutive; calling unique alone on an unsorted array does not globally deduplicate it.

3. 3. Look up each rank

   Use lower_bound in the sorted keys to find each original value. Every original value is guaranteed present, so iterator subtraction gives its zero-based rank. For [100,−5,100,7], dictionary [−5,7,100] produces ranks [2,0,2,1]. Both occurrences of 100 share a rank. Lower-bound search costs O(log d) for each lookup.

4. 4. State what is and is not preserved

   a<b exactly when rank(a)<rank(b), and equal originals get equal ranks. However, gaps change: 100−7 is 93 while rank(100)−rank(7) is 1. Area, distance and length calculations must use original coordinates or stored gap widths. For a later threshold value not present in keys, lower/upper bound gives an insertion boundary, not necessarily an existing exact key.

5. 5. Prepare indexed data structures

   A zero-based rank can index a frequency vector directly. A conventional one-based Fenwick tree should receive rank+1, because Fenwick index zero has a different role. Compression needs the relevant keys known in advance; a genuinely new online value may require rebuilding ranks or using an ordered dynamic structure. Do not silently append a rank that breaks sorted order.

This is a complete program. Compile with C++17 and enter the input described below.

// Key idea: 5. Prepare indexed data structures A zero-based rank can index a frequency vector
// directly.
#include<iostream>
#include<vector>
#include<algorithm>
int main(){
    int n;
    std::cin>>n;
    std::vector<long long>original(n);
    for(auto&x:original){
        std::cin>>x;
    }
    auto keys=original;
    std::sort(keys.begin(),keys.end());
    keys.erase(std::unique(keys.begin(),keys.end()),keys.end());
    for(int i=0;i<(int)keys.size();++i){
        std::cout<<keys[i]<<(i+1==(int)keys.size()?'\n':' ');
    }
    if(keys.empty()){
        std::cout<<'\n';
    }
    for(int i=0;i<n;++i){
        int rank=std::lower_bound(keys.begin(),keys.end(),original[i])-keys.begin();
        std::cout<<rank<<(i+1==n?'\n':' ');
    }
    if(n==0){
        std::cout<<'\n';
    }
}

Complexity analysis

O(n log(n+1)) preprocessing time from sorting plus n logarithmic lookups; O(n) memory for original values and dictionary. A lookup after building keys is O(log d), and indexed operations then depend on the chosen structure. Compression alone is not O(1) dynamic ordered-key insertion.

Example input and output

Read n (0..200000), then n signed keys with |key|≤10^12. Print sorted distinct dictionary values, then each input value’s zero-based rank. Empty input produces two blank lines.

Input

4
100 -5 100 7

Output

-5 7 100
2 0 2 1

Ranks follow the ordered dictionary; both copies of 100 map to 2.

Practical applications

Use when a problem depends on equality/order of many known sparse large values and needs compact indexing. Keep physical coordinates for lengths/areas. A map supports unseen ordered online keys but does not automatically provide dense rank queries; an order-statistic structure is a separate tool.

Check your understanding

Which property does compression preserve?

Put it into practice

Build a frequency array indexed by the produced ranks and decode each distinct key’s count.