離散化

#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 1000010;
int n, m;
vector<int> originalValues;
vector<int> addedValues;
vector<int> startPos, endPos;
vector<long long> diffArray;

bool canProcess(int limit)
{
    fill(diffArray.begin(), diffArray.end(), 0);
    
    for (int i = 0; i < limit; i++)
    {
        diffArray[startPos[i]] += addedValues[i];
        diffArray[endPos[i] + 1] -= addedValues[i];
    }
    
    for (int i = 1; i <= n; i++) diffArray[i] += diffArray[i - 1];
    
    for (int i = 1; i <= n; i++)
    {
        if (diffArray[i] > originalValues[i]) return false;
    }
    
    return true;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    originalValues.resize(MAX_N);
    addedValues.resize(MAX_N);
    startPos.resize(MAX_N);
    endPos.resize(MAX_N);
    diffArray.resize(MAX_N);
    
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> originalValues[i];
    
    for (int i = 1; i <= m; i++)
    {
        cin >> addedValues[i] >> startPos[i] >> endPos[i];
    }
    
    if (canProcess(m))
    {
        cout << 0 << endl;
        return 0;
    }
    
    int left = 1, right = m;
    while (left <= right)
    {
        int mid = (left + right) >> 1;
        if (canProcess(mid)) left = mid + 1;
        else right = mid - 1;
    }
    
    cout << -1 << '\n' << left << endl;
    return 0;
}

離散化が必要な理由

プログラムの扱うデータの範囲が \(-10^9\) から \(10^9\) まで広がる場合、配列を直接確保して数をカウントすることは現実的ではありません。このような広範囲のデータを効率的に処理するために、離散化という手法が活躍します。

離散化の本質は、広範囲に分布する値を連続した狭い範囲の整数に変換することです。例えば、\(-1230384328\) という大きな負の数を \(3\) という小さなインデックスにマッピングできます。こうすることで、\(values[3] = -1230384328\) として保存し、カウント時には \(counter[3]++\) と简单地処理できるようになります。

離散化における重要な問題点

広範囲のデータを効果的に離散化するには、2つの主要な課題に対処する必要があります。

課題1：効率的なマッピングと一意性の確保

複数の異なる値が同じインデックスに割り当てられることを防ぎながら、高速な変換を実現する必要があります。この解決策は、値をソートしてから重複を取り除くことです。昇順に並べられた配列を用意すれば、各値に一意のインデックスを付与できます。

課題2：マッピング後のインデックス取得

元の値が離散化後の配列のどの位置にあるかを迅速に見つける必要があります。ソートが完了しているため、二分探索アルゴリズムを適用できます。または、ハッシュテーブルを使用して \(O(1)\) での検索を実現することも可能です。

実践例：区間和の計算

以下のコードは、離散化を使用して区間和を効率的に計算する方法をを示しています。

#include <bits/stdc++.h>
using namespace std;

using ValuePair = pair<int, int>;

const int MAX_SIZE = 300010;
vector<int> compressedValues;
vector<ValuePair> additions, queries;
vector<int> values, prefixSums;
int elementCount, operationCount;

int getIndex(int target)
{
    int left = 0, right = (int)compressedValues.size() - 1;
    
    while (left <= right)
    {
        int mid = (left + right) >> 1;
        if (compressedValues[mid] > target) right = mid - 1;
        else left = mid + 1;
    }
    
    return right + 1;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    values.resize(MAX_SIZE);
    prefixSums.resize(MAX_SIZE);
    
    cin >> elementCount >> operationCount;
    
    for (int i = 1; i <= elementCount; i++)
    {
        int position, delta;
        cin >> position >> delta;
        compressedValues.push_back(position);
        additions.push_back({position, delta});
    }
    
    for (int i = 1; i <= operationCount; i++)
    {
        int leftBound, rightBound;
        cin >> leftBound >> rightBound;
        compressedValues.push_back(leftBound);
        compressedValues.push_back(rightBound);
        queries.push_back({leftBound, rightBound});
    }
    
    sort(compressedValues.begin(), compressedValues.end());
    compressedValues.erase(
        unique(compressedValues.begin(), compressedValues.end()),
        compressedValues.end()
    );
    
    for (const auto& entry : additions)
    {
        int idx = getIndex(entry.first);
        values[idx] += entry.second;
    }
    
    for (int i = 1; i <= (int)compressedValues.size(); i++)
        prefixSums[i] = prefixSums[i - 1] + values[i];
    
    for (const auto& query : queries)
    {
        int leftIdx = getIndex(query.first);
        int rightIdx = getIndex(query.second);
        cout << prefixSums[rightIdx] - prefixSums[leftIdx - 1] << endl;
    }
    
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

using ValuePair = pair<int, int>;

const int MAX_SIZE = 300010;
vector<int> compressedValues;
vector<ValuePair> additions, queries;
unordered_map<int, int> indexMap;
vector<int> values, prefixSums;
int elementCount, operationCount;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    values.resize(MAX_SIZE);
    prefixSums.resize(MAX_SIZE);
    
    cin >> elementCount >> operationCount;
    
    for (int i = 1; i <= elementCount; i++)
    {
        int position, delta;
        cin >> position >> delta;
        compressedValues.push_back(position);
        additions.push_back({position, delta});
    }
    
    for (int i = 1; i <= operationCount; i++)
    {
        int leftBound, rightBound;
        cin >> leftBound >> rightBound;
        compressedValues.push_back(leftBound);
        compressedValues.push_back(rightBound);
        queries.push_back({leftBound, rightBound});
    }
    
    sort(compressedValues.begin(), compressedValues.end());
    compressedValues.erase(
        unique(compressedValues.begin(), compressedValues.end()),
        compressedValues.end()
    );
    
    for (int i = 0; i < (int)compressedValues.size(); i++)
        indexMap[compressedValues[i]] = i + 1;
    
    for (const auto& entry : additions)
    {
        int idx = indexMap[entry.first];
        values[idx] += entry.second;
    }
    
    for (int i = 1; i <= (int)compressedValues.size(); i++)
        prefixSums[i] = prefixSums[i - 1] + values[i];
    
    for (const auto& query : queries)
    {
        int leftIdx = indexMap[query.first];
        int rightIdx = indexMap[query.second];
        cout << prefixSums[rightIdx] - prefixSums[leftIdx - 1] << endl;
    }
    
    return 0;
}