C++でq回の範囲更新操作を適用した後の配列内の異なる値の個数を求める方法

問題概要

この問題では、すべての要素が0で初期化されたサイズNの配列と、次の形式のQ個のクエリが与えられます。

update(s, e, val) → インデックスsからe(両端を含む)までのすべての要素をvalに更新するクエリです。

私たちのタスクは、指定された操作をq回適用した後の配列に含まれる異なる値の個数を求めることです。

例を使って問題を理解しましょう。

入力 : N = 6, Q = 2
Q1 = update(1, 4, 3)
Q2 = update(0, 2, 4)

出力 : 3

説明

初期配列:arr[] = {0, 0, 0, 0, 0, 0}

クエリ1:update(1, 4, 3) → arr[] = {0, 3, 3, 3, 3, 0}

クエリ2:update(0, 2, 4) → arr[] = {4, 4, 4, 3, 3, 0}

最終的な配列には「0」「3」「4」の3種類の値が含まれているため、答えは3となります。

解法アプローチ

1. シンプルな解法(シミュレーション)

最も単純な解決策は、各クエリを配列に対してそのまま実行し、その後、補助配列やsetなどを用いて配列内のユニークな値の個数を数え、その個数を返す方法です。

この方法は正しく動作しますが、1回の範囲更新に最大O(N)の計算量がかかるため、クエリ数が多い場合には非効率になります。

2. 効率的な解法(遅延伝播を用いたセグメントツリー)

より効率的なアプローチは、遅延伝播(lazy propagation)の概念を活用して、クエリにおける範囲操作を最適化する方法です。セグメントツリーを0で初期化しておき、更新操作が実行されるたびに対応するノードの値を更新します。区間全体が同じ値で塗りつぶされた場合は、そのノードに値を記録するだけで、子への伝播を後回しにできます。

すべてのクエリ処理が完了した後、ツリーを根から走査し、各ノードが保持する値をsetに挿入していけば、setのサイズがすなわち配列内の異なる値の個数となります。

実装例

以下は、この解法の動作を示すC++プログラムです。

#include <bits/stdc++.h>
using namespace std;
#define N 100005
int lazyST[4 * N];
set<int> diffNo;
void update(int s, int e, int val, int idx, int l, int r){
    if (s >= r or l >= e)
        return;
    if (s <= l && r <= e) {
        lazyST[idx] = val;
        return;
    }
    int mid = (l + r) / 2;
    if (lazyST[idx])
        lazyST[2 * idx] = lazyST[2 * idx + 1] = lazyST[idx];
    lazyST[idx] = 0;
    update(s, e, val, 2 * idx, l, mid);
    update(s, e, val, 2 * idx + 1, mid, r);
}
void query(int idx, int l, int r){
    if (lazyST[idx]) {
        diffNo.insert(lazyST[idx]);
        return;
    }
    if (r - l < 2)
        return;
    int mid = (l + r) / 2;
    query(2 * idx, l, mid);
    query(2 * idx + 1, mid, r);
}
int main() {
    int n = 6, q = 3;
    update(1, 3, 5, 1, 0, n);
    update(4, 5, 1, 1, 0, n);
    update(0, 2, 9, 1, 0, n);
    query(1, 0, n);
    cout << "操作後の配列に含まれる異なる値の個数は " << diffNo.size();
    return 0;
}

出力

操作後の配列に含まれる異なる値の個数は 3

まとめ

遅延伝播を用いたセグメントツリーを採用することで、各範囲更新クエリをO(log N)で処理でき、単純なシミュレーション(1クエリあたりO(N))に比べて大幅に高速化されます。すべてのクエリ処理後にツリーを一度走査するだけで、配列内の異なる値の個数を効率的に求めることができます。