C ++で指定された操作をq回適用した後、配列内の異なる数の数を見つけます

この問題では、すべてゼロで構成される配列のサイズである数値Nが与えられ、次のタイプのそれぞれのQクエリが与えられます-

update（s、e、val）->このクエリは、すべての要素をsからe（両方を含む）からvalに更新します。

私たちのタスクは、指定された操作をq回適用した後、配列内の異なる数の数を見つけることです。

問題を理解するために例を見てみましょう

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

Output : 2

説明

初期配列、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で初期化すると、操作時に更新されている値が目的の値を返します。これが、ソリューションをより詳しく説明するプログラムです。

例

ソリューションの動作を説明するプログラム

#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<<"The number of different numbers in the array after operation is "<<diffNo.size();
   return 0;
}

出力

The number of different numbers in the array after operation is 3